Split Array Largest Sum

Partition the array, preserving order, into exactly K non-empty contiguous segments, minimizing the sum of the segment maximums; this is not minimizing the maximum segment sum.

输入格式

The first line contains n K, and the second line contains n numbers. The original bounds are 1<K≤n<300 and 1<a[i]<10^5, yet the original example contains 1; to accommodate that example, this site uses 2≤K≤n≤299 and 1≤a[i]≤99999, keeping the entire original strict domain.

输出格式

Output a single integer answer.

样例 1

输入：

5 2
1 5 3 4 2

输出：

6

样例 2

输入：

3 3
2 2 2

输出：

6

样例 3

输入：

3 2
9 1 2

输出：

11

样例说明

The outputs of the three public examples are, in order: 6; 6; 11. Checked by independent enumeration or direct simulation.