传说一千多年前，St. Patrick 将 Mooland 的蛇全部驱逐。然而，蛇后来又回到了 Mooland！圣帕特里克节是 3 月 17 日，因此 Bessie 决定彻底驱逐 Mooland 的所有蛇，以纪念 St. Patrick。

Bessie 带着一张网，要捕捉沿一条直线分布的 $N$ 群蛇 $(1 \leq N \leq 400)$。她必须按照各群在线上的顺序捕捉每一群中的所有蛇。每捕捉一群后，她可以把蛇放入笼子，用空网开始捕捉下一群。

大小为 $s$ 的网可以捕捉含有 $g$ 条蛇的一群，其中 $g \leq s$。但是，用大小为 $s$ 的网捕捉大小为 $g$ 的一群蛇时，会浪费 $s - g$ 的空间。Bessie 的网最初可以是任意大小，她可以改变网的大小 $K$ 次 $(1 \leq K < N)$。

请告诉 Bessie，捕捉所有群后，累积浪费的空间总量最少是多少。

输入格式

第一行包含 $N$ 和 $K$。第二行包含 $N$ 个整数 $a_1,\dots,a_N$，其中 $a_i$（$0 \leq a_i \leq 10^6$）是第 $i$ 群的蛇数。

输出格式

输出一个整数，表示 Bessie 捕捉所有蛇后浪费的空间最小值。

样例

输入格式 1

6 2
7 9 8 2 3 2

输出格式 1

3

说明

Bessie 的网最初大小为 7。捕捉第一群后，她将网改为大小 9，并保持到第 4 群，此时改为大小 3。浪费的空间总量为 $(7-7) + (9-9) + (9-8) + (3-2) + (3-3) + (3-2) = 3.$

题目作者：Patrick Zhang