题目描述

桌上放了 $N$ 件物品，从左到右依次标号 $1\sim N$。第 $i$ 件物品的大小为 $a_i$。

你有一个背包，每次你可以用背包装上恰好一个物品带走。

你作为一个强迫症患者，必须按照从左到右的顺序带走所有的物品。

你作为一个魔法少女，可以设定你背包的初始容量，并在每次搬运前可以修改你的背包容量。当然，你的魔法能量有限，最多只能修改 $K$ 次背包的容量（不包括初始设定）。

你作为一个有强迫症的魔法少女，希望每次浪费的背包容量的总和尽可能小。形式化的，你需要最小化 $\sum_{i=1}^N (S_i-a_i)$，其中 $S_i$ 为你搬运第 $i$ 件物品时的背包容量。显然，你需要保证背包的容量大于搬运的物品的大小，即 $S_i \ge a_i$。

相信你作为一个会算法的魔法少女，很快就能解决这个问题。

输入

第一行包含两个整数 $N, K(1\le K\le N\le 400)$。

接下来一行 $N$ 个整数 $a_1,a_2,\dots,a_N(0\le a_i\le 10^6)$，表示每个物品的大小。

输出

输出一个整数表示答案。

6 2
7 9 8 2 3 2

3

样例解释

你可以设定初始容量为 $7$，在第二次搬运时修改为 $9$，在第四次搬运时修改为 $3$，这样答案为 $(7-7)+(9-9)+(9-8)+(3-2)+(3-3)+(3-2)=3$.