Snake Clearing

Legend has it that thousands of years ago, Saint Patrick rids the land of all snakes in Mooland. However, the snakes have made a comeback! Since Saint Patrick's Day is celebrated on March 17th every year, Bessie wants to commemorate the occasion by completely clearing out all the snakes from Mooland.

Bessie is equipped with a net to capture N groups of snakes arranged in a row, where N satisfies \(1 \le N \le 400\). She must capture the groups in the order they appear. After capturing a group, she deposits the snakes into a cage and resets her net for the next group.

A net of size \(s\) can capture any group containing \(g\) snakes provided \(g \le s\). However, if Bessie uses a net of size \(s\) to capture a group of \(g\) snakes, she wastes \(s - g\) units of capacity. Bessie can initially set the net to any size, and she is allowed to change the net size at most \(K\) times (with \(1 \le K < N\)). Changing the net size effectively partitions the groups into \(K+1\) segments. For each segment, an optimal strategy is to set the net size to the maximum number of snakes in that segment, which minimizes the waste.

The waste for a segment covering groups from index \(i\) to \(j\) (inclusive) is given by:

[ \text{waste}(i, j) = (j - i + 1) \times \max_{i \le k \le j}(a_k) - \sum_{k=i}^{j} a_k ]

Help Bessie determine the minimum total wasted space after capturing all the snake groups.

inputFormat

The input consists of two lines.

• The first line contains two integers, \(N\) and \(K\), where \(N\) is the number of snake groups and \(K\) is the number of allowed net size changes.
• The second line contains \(N\) integers \(a_1, a_2, \ldots, a_N\), representing the number of snakes in each group.

outputFormat

Output a single integer: the minimum total wasted space after capturing all snake groups.

sample

3 1
2 3 1

1