[usaco2005 open]Landscaping 地形改造

有 $N$ 块依次排列的土地，第 $i$ 块土地的初始海拔为 $h_i$。你可以从任意土地中移走任意数量的土，但不能向其中填土。设第 $i$ 块土地改造后的海拔为 $g_i$，则必须满足 $0\le g_i\le h_i$。

如果一段连续区间 $[l,r]$ 内所有土地的最终海拔均相同，且该海拔严格高于区间两侧所有存在的相邻土地，即位置 $l-1$ 和 $r+1$（如果存在）的最终海拔，同时该区间至少存在一个相邻位置，则称这段区间为一个山顶。

你需要使最终地形中的山顶数量不超过 $K$，并最小化移走的土的总量：

$$\sum_{i=1}^{N}(h_i-g_i)。$$

输入格式

第一行输入两个整数 $N$ 和 $K$。

接下来 $N$ 行，每行输入一个整数，其中第 $i$ 行表示第 $i$ 块土地的初始海拔 $h_i$。

输出格式

输出一个整数，表示在最终地形的山顶数量不超过 $K$ 的条件下，最少需要移走的土的总量。

样例输入

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

样例输出

5

数据范围

• $1\le N\le 1000$；
• $1\le K\le \min(N,25)$；
• $0\le h_i\le 10^6$；
• 所有输入均为整数。

来源与许可

本题为 USACO 2005 Open 试题「Landscaping 地形改造」，题面与测试数据整理自 BZOJ。

样例 1

输入

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

输出

5