想象一下,您的城市是一个具有笛卡尔坐标系的无限二维平面。您所在城市唯一受犯罪影响的道路是 x 轴。目前,沿路有n名犯罪分子。这条路上还没有建警察局,所以市长想建一个。
由于你将负责这个新的警察局,市长要求你选择一个合适的位置(某个整数点)来建造它。你应该选择警察局的最佳位置,这样你就可以最大限度地减少抓捕犯罪任务的总时间。你抓捕罪犯的任务只能在这个车站进行。
新车站将只有一辆巡逻车。你将乘这辆车去见罪犯,把他们抬上车,带回警察局,关进监狱。巡逻车一次最多可运载 m 名罪犯。请注意,犯罪分子并不知道您的任务。所以,他们不会逃跑,而是留在原地。
你的任务是找到警察局的位置,这样你抓捕所有罪犯所需的总距离就会尽可能小。请注意,您还可以在一名或多名罪犯已经存在的位置上建立警察局。在这种情况下,所有这些罪犯都会立即被捕。
输入
输入的第一行将包含两个由空格分隔的整数 n (1 ≤ n ≤ 106) 和 m (1 ≤ m ≤ 106)。下一行将包含 n 个由空格分隔的整数。第 i 个整数是第 i 个罪犯在 x 轴上的位置。位置的绝对值不会超过109。如果犯罪分子的位置为x,则他/她位于平面的点(x,0)。
罪犯的职位将以非降序排列。请注意,飞机的某个位置可能有不止一名犯罪分子。
注意:由于输入/输出的大小可能非常大,因此请勿在您的语言中使用慢速输入/输出技术。例如,不要在 C++ 中使用输入/输出流(cin、cout)。
输出
打印一个整数,这意味着抓获所有罪犯所需的最小可能距离。
示例
输入 #1
3 6 1 2 3
输出 #1
4
输入 #2
5 5 -7 -6 -3 -1 1
输出 #2
16
输入 #3
1 369 0
输出 #3
0
输入#4
11 2 -375 -108 1336 1453 1598 1892 2804 3732 4291 4588 4822
输出#4
18716