Minimize Total Input Cost (for LTMS)

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. Each segment corresponds to one week of activities. 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 original has no numeric bounds; this site adds 0≤n,k≤300, 0≤a[i]≤10^9. 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 3
1000 500 2000 8000 1500

输出：

9500

样例 2

输入：

0 0

输出：

0

样例 3

输入：

2 3
1 2

输出：

-1

样例说明

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