题目描述

农夫约翰正在做一次艰难的转型，从养山羊改成养奶牛，他的农场，由于是为养山羊而设计的所以有太多的山，为了养牛就必须将它整平。但是，将山整平是件很花钱的工作，所以他要移走尽可能少的土。
由于农场很细长，所以可以用一个 $n$ 和 $n$ 个整数（范围 $[1,10^6]$）组成的二维的数组来表示，如：

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

上述农场的侧面图是这样的：

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

一个或是一些连续等高的地面，如果它左边或是右边的海拔都比它低的话，就被称为山顶，上面的例子就有三个山顶。 确定如果要使地图上仅有 $k$ 个山顶，至少要移走多少体积的土（每块地面减少一单位海拔需移走一单位的土）。注意，地面的海拔只能被降低不能被升高。 对于例子，如果要减少到只有 $1$ 个山顶，这需要移走 $2+1+1+1=5$ 个单位的土：

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

其中 - 表示移走的土。

输入格式

第 $1$ 行输入整数 $n$ 和 $k$。之后 $n$ 行，每行输入一个整数，表示这块地的海拔。

输出格式

如果仅能有 $k$ 个山顶至少要移走多少土。

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

5

数据规模与约定

对于 $100\%$ 的数据，$1 \le n \le 10^3$，$1 \le k \le 25$。

题目来源

Gold