AT_tenka1_2016_qualB_e 天下一合体

[problemUrl]: https://atcoder.jp/contests/tenka1-2016-qualb/tasks/tenka1_2016_qualB_e タカハシ君は長さ $ N $ の数列 $ a_1,\ a_2,\ ...,\ a_N $ を持っています。そして以下の動作を何度も行います。 - 数列から、隣り合う $ 2 $ つの要素を選ぶ。そしてその $ 2 $ つの要素を足して $ 1 $ つにする。つまり $ 2 $ つの要素を、要素の和を値に持つ $ 1 $ つの要素で置き換える。 なお、操作は数列の要素数が $ M $ 未満にならない限り好きな回数行えます。 タカハシ君は数列の各要素の絶対値の合計を最小化したいです。あなたの仕事はタカハシ君の代わりに、この最小を求めることです。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ a_1 $ $ a_2 $ ... $ a_N $

$ 1 $ 行に求めた答えを出力してください。 出力の末尾に改行を入れること。

### 制約 - $ 1\ ≦\ N\ ≦\ 20,000 $ - $ 1\ ≦\ M\ ≦\ min(100,\ N) $ - $ |a_i|\ ≦\ 10^9 $ ### Sample Explanation 1 \- 最初は\\\[2, -4, 3, -1\\\]の1つ目と2つ目の要素を選びます。すると\\\[-2, 3, -1\\\]になります。 - 次に\\\[-2, 3, -1\\\]の1つ目と2つ目の要素を選びます。すると\\\[1, -1\\\]になります。 すると求める値は $ |1|\ +\ |-1|\ =\ 2 $ になり、これが最適です。 ### Sample Explanation 2 \- 2つ目と3つ目の要素を選ぶ操作を5回行います。すると\\\[0, -1, 5, -4\\\]になります。 - 次に3つ目と4つ目を選び\\\[0, -1, 1\\\]にします。 すると求める値は $ |0|\ +\ |-1|\ +\ |1|\ =\ 2 $ になり、これが最適です。