隐匿行迹

信标折叠了，但Zero还在追踪——它通过每个人的行动轨迹，识别个体。

"要隐匿。"你说，"把我们的行迹混在人群里，让Zero分不清谁是谁。"

"咋隐匿？"

"分组。"你说，"每组成员至少$k$人。同一组的人，行动轨迹被替换成组的中位数轨迹。"

"替换成一样的？"

"对。"你说，"Zero看到一组人都走同样的路线，就分不清谁是谁了。"

"代价？"

"每个人偏离中位轨迹的距离。"你说，"总偏离要最小。"

"中位轨迹？"

"对。"你说，"一组人的坐标，中位数是中间那个人的坐标。所有人向中间靠拢，总移动距离最小。"

"这跟估测断层一样？"

"类似。"你说，"但约束更强——每组至少$k$人。"

"不能一个人一组。"

"对。"你说，"必须隐匿在群体里。"

你开始写。$dp[i]$为前$i$个人分组的最小偏离。$dp[i]=\min(dp[j]+cost(j+1,i))$，其中$i-j\ge k$。

"前3个人。"你说，"坐标1,3,5。如果$k=3$，只能一组。中位数3。偏离=2+0+2=4。"

"前6个人。"你说，"坐标1,3,5,7,9,11。$k=3$。可以分两组：(1,3,5)和(7,9,11)。各偏离4。总偏离8。"

"或者一组全包：中位数5或7。偏离大得多。"

"所以分两组好。"

"对。"

CC看着你的分组——把团队分成3人一组，像作战小队。

"我和Echo一组？"她问。

"不。"你说，"你、我、Echo各在不同组——分散风险。"

"那谁保护Echo？"

"她自己。"你说，"还有组里的另外两个人。"

"我不放心。"

"我也不放心。"你说，"但隐匿比保护重要。"

Echo的投影分成了三份——一份跟着你，一份跟着CC，一份留在原地。

"我同时在三个组。"她说，"但Zero只能看到一个。"

"看到哪个？"

"看到你们需要的那个。"她说，"我随时切换。"

"累吗？"

"累。"她说，"但值得。"

题目描述

给定$n$个人的坐标，要分成若干组。每组至少$k$人。每组内所有人变为该组中位数坐标。最小化总移动距离。

输入格式

$n,k$。然后$n$个整数表示坐标。

输出格式

最小总移动距离。

输入样例

3
1 2 3

输出样例

0
0
0

提示

• 斜率优化DP。
• $dp[i]$为前$i$个人分组的最小代价。
• $dp[i]=\min(dp[j]+cost(j+1,i))$，其中$i-j\ge k$。
• $cost$为中位数代价，预处理前缀和。
• 维护下凸壳优化。