Efficient Cost

Cut the entire integer array, keeping its original order, into non-empty contiguous segments, each of length ≤threshold; the cost of a segment is its maximum value. Find the minimum total cost over all segments. Negative integers are allowed, and segment lengths are not forced to equal the limit.

输入格式

The first line contains n threshold, and the second line contains the array. This site adds 1≤threshold≤n≤5000 and −10⁹≤element≤10⁹.

输出格式

Output the single integer required by the problem.

样例 1

输入：

6 3
1 3 4 5 2 6

输出：

10

样例 2

输入：

3 3
-1 -2 -3

输出：

-6

样例 3

输入：

4 3
10 1 1 10

输出：

20

样例说明

The answers to the three public examples are, in order: 10; -6; 20. The examples were rechecked by independent enumeration, state search, or direct simulation.