傳說一千多年前，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