你在打音游,这一关有 n 个音符,会从屏幕的最上方落下,你需要在屏幕最下方的线上打到这些音符。
判定线可以看作数轴的正半轴,n 个音符依次落下,第 i 个音符会落到 pi 的位置。你的两只手可以分别覆盖两个长度为 L 的区间,准确来说,一只手可以覆盖 [x,x+L],使得当音符落在这个区间(包括端点)的时候可以准确打到。
游戏开始时你的两只手覆盖了 [0,L],在接下来的 n 个音符落下的间隙中,你可以将你的手任意移动,移动的时间忽略不计,从 [x,x+L] 移动到 [y,y+L] 需要耗费 |x−y| 的体力。
游戏开始前,你想要知道最少耗费多少体力可以依次打到所有的音符。
输入格式
第一行两个整数 n,L。
第二行 n 个整数,第 i 个整数 pi 表示第 i 个音符的位置。
输出格式
一行一个整数表示最少耗费的体力。
样例输入 1
4 1
6 3 7 1
样例输出 1
9
样例解释
两只手的移动分别是:[0,1]→[5,6]→[6,7] 和 [0,1]→[2,3]→[1,2],花费体力 6+3=9。
样例输入 2/3
见下发文件 ex_game2/3.in
样例输出2/3
见下发文件 ex_game2/3.out
数据范围
对于 100% 满足 1≤n≤50000,0≤L≤50,0≤pi≤109
subtask1(15%):n≤200,pi≤200
subtask2(15%):L=0
subtask3(30%):L≤5
subtask4(40%):无特殊限制。
时间限制:3000ms
空间限制:512MB