K blocks#7473
You are given a sequence of positive integers. Let's define the "value of a splitting" of the sequence into blocks as the sum of maximums in each of the blocks. For a given , find the minimal possible value of a splitting.
First line contains two integers and (1 \le n \le 10^5, 1 \le k \le \min(n, 100)). Next line contains integers A_1, A_2, \ldots, A_n (1 \le A_i \le 10^6) - the sequence elements.
Output one number - minimal possible value of a splitting.
Example 1
Example 2