問題文

タカハシ君は長さ 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

入力例 1

4 2
2 -4 3 -1

出力例 1

2

• 最初は[2, -4, 3, -1]の1つ目と2つ目の要素を選びます。すると[-2, 3, -1]になります。
• 次に[-2, 3, -1]の1つ目と2つ目の要素を選びます。すると[1, -1]になります。

すると求める値は |1| + |-1| = 2 になり、これが最適です。

入力例 2

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

出力例 2

2

• 2つ目と3つ目の要素を選ぶ操作を5回行います。すると[0, -1, 5, -4]になります。
• 次に3つ目と4つ目を選び[0, -1, 1]にします。

すると求める値は |0| + |-1| + |1| = 2 になり、これが最適です。

入力例 3

5 5
1000000000 1000000000 1000000000 1000000000 1000000000

出力例 3

5000000000