Problem Description

Farmer John is going through a difficult transition: he is switching from raising goats to raising dairy cows. His farm was designed for goats, so it has too many hills. To raise cows, he must level the land. However, leveling hills is expensive, so he wants to remove as little soil as possible.

Because the farm is very long and narrow, it can be represented by an integer $n$ and a two-dimensional array consisting of $n$ integers (in the range $[1,10^6]$), for example:

1 2 3 3 3 2 1 3 2 2 1 2

The side view of the farm above looks like this:

    * * *     *
  * * * * *   * * *   *
* * * * * * * * * * * *
1 2 3 3 3 2 1 3 2 2 1 2

One or more consecutive pieces of land with the same height are called a peak if the heights on both its left and right sides are lower than it. In the example above, there are three peaks. Determine the minimum amount of soil that must be removed so that the map contains only $k$ peaks (reducing the height of a piece of land by $1$ requires removing $1$ unit of soil). Note that heights can only be lowered, not raised. For the example, if we want to reduce it to only $1$ peak, we need to remove $2+1+1+1=5$ units of soil (- indicates removed soil):

    * * *     -
  * * * * *   - - -   -
* * * * * * * * * * * *
1 2 3 3 3 2 1 3 2 2 1 2

Input Format

The first line contains integers $n$ and $k$.

Then follow $n$ lines, each containing one integer, representing the height of that piece of land.

Output Format

Output the minimum amount of soil that must be removed so that there are only $k$ peaks.

12 1
1
2
3
3
3
2
1
3
2
2
1
2

5

Hint

For $100\%$ of the testdata, $1 \leq n \leq 10^3$，$1 \leq k \leq 25$.

Translated by ChatGPT 5