You are given an array of n integers. You need to divide it into k non-empty subsegments (a sequence of consecutive elements) so that:
1) Each element of the array was included in exactly one subsegment.
2) If for each subsegment we choose the minimum number in it, then the sum of all minima should be the maximum possible.
Report the sum of the minima of the values in the subsegments of this partition.
Input:
The first line contains two natural numbers - n (1 <= n <= 500) and k (1 <= k <= n).
The second line contains n integers - the elements of the array a
i (1 <= a
i <= 10
5).
Output:
Print one number - the answer to the problem.
Example:
| Input |
Output |
5 3
4 2 5 1 3
| 8 |
Explanation:
One of the suitable partitions: [4, 2], [5], [1, 3]. The sum of the minima in each sub-segment is 2 + 5 + 1 = 8.