← 返回题目列表

AtCoder · tenka1_2016_qualB_e

E. 天海一联盟

中文机器翻译题面 查看原题

配点 : 900 点

問題文

高桥长 N 序列 我有 a_1, a_2, ..., a_N 。然后一遍又一遍地重复以下动作。

  • 从序列来看,相邻 2 选择一个元素。还有那个 2 添加两个元素 1 。换句话说 2 有两个元素,其值为元素之和 1 替换为一个元素。

当序列中的元素数量为 只要不小于 M ,您可以多次执行。

高桥想要最小化序列中每个元素的绝对值之和。你的工作就是代表高桥找到这个最小值。 打印您在

制約

  • 1 ≦ N ≦ 20,000
  • 1 ≦ M ≦ min(100, N)
  • |a_i| ≦ 10^9

入力

输入是按以下格式从标准输入给出的。

N M
a_1 a_2 ... a_N

出力

1 行找到的答案。 在输出末尾插入换行符。


入力例 1

4 2
2 -4 3 -1

出力例 1

2
  • 初始选择[2,-4,3,-1]的第一个和第二个元素。那么它就变成了[-2,3,-1]。
  • 接下来,选择 [-2, 3, -1] 的第一个和第二个元素。那么就变成了[1,-1]。

那么要查找的值为 |1| + |-1| = 2 ,这是最佳的。


入力例 2

9 3
0 3 -5 -1 5 0 -3 5 -4

出力例 2

2
  • 选择第二个和第三个元素五次。那么就变成了[0,-1,5,-4]。
  • 接下来,选择第三个和第四个并将它们设置为 [0, -1, 1]。

那么要查找的值为 |0| + |-1| + |1| = 2 ,这是最佳的。


入力例 3

5 5
1000000000 1000000000 1000000000 1000000000 1000000000

出力例 3

5000000000