Split Array Largest Sum

Keeping the input order, split the array into exactly k non-empty contiguous segments, where the cost of each segment is its maximum element; find the minimum total cost over all segments. Note that this is not the similarly named problem of minimizing the largest segment sum. Added by this site: output −1 when there is no solution, and output 0 when an empty array is split into 0 segments.

输入格式

The input gives n k and n non-negative integers. The full original bounds are kept: 0≤n,k≤300, 0≤a[i]≤100000. The cases k>n, n=0, and k=0 are not excluded and are handled by the protocol above.

输出格式

Output one integer answer.

样例 1

输入：

5 2
1 2 3 4 5

输出：

6

样例 2

输入：

0 0

输出：

0

样例 3

输入：

2 3
1 2

输出：

-1

样例说明

The outputs of the three public examples are, in order: 6; 0; -1. They have been checked by independent enumeration or direct simulation.