Problem Description

Takahashi has a sequence of numbers of length $ N $, which is $a_1,\ a_2,\ ...,\ a_N$. He repeatedly performs the following operation:

• From the sequence, choose two adjacent elements and merge them into one element, which has the value of the sum of the two chosen elements.

Note that the operation can be performed any number of times as long as the number of elements in the sequence does not fall below $ M $.

Takahashi wants to minimize the sum of the absolute values of the elements in the sequence. Your task is to find this minimum sum on behalf of Takahashi.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ a_1 $ $ a_2 $ ... $ a_N $

Output Format

Output the answer in one line. Make sure to include a newline at the end of the output.

Sample Input and Output

Sample Input #1

4 2
2 -4 3 -1

Sample Output #1

2

Sample Input #2

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

Sample Output #2

2

Sample Input #3

5 5
1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output #3

5000000000

Notes/Hints

Constraints

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

Sample Explanation 1

• Initially, choose the first and second elements of \[2, -4, 3, -1\]. This results in \[-2, 3, -1\].
• Next, choose the first and second elements of \[-2, 3, -1\]. This results in \[1, -1\].
  The desired value is $|1|\ +\ |-1|\ =\ 2$, which is optimal.

Sample Explanation 2

• Perform the operation of choosing the second and third elements five times. This results in \[0, -1, 5, -4\].
• Next, choose the third and fourth elements to get \[0, -1, 1\].
  The desired value is $|0|\ +\ |-1|\ +\ |1|\ =\ 2$, which is optimal.

见题面 Input 部分

见题面 Output 部分