伝説によると、千年以上前に St. Patrick は Mooland からすべてのヘビを追放しました。しかしヘビは戻ってきました！聖パトリックの日は 3 月 17 日だったので、Bessie は Mooland のヘビをすべて完全に追放して St. Patrick を記念します。

Bessie は一直線上の $N$ 群のヘビ $(1 \leq N \leq 400)$ を捕まえる網を持っています。群が線上に並ぶ順番で、各群のすべてのヘビを捕まえなければなりません。群を捕まえるたびに、ヘビをかごに入れ、次の群は空の網で捕まえられます。

大きさ $s$ の網では、ヘビが $g$ 匹いる群を $g \leq s$ の場合に捕まえられます。しかし大きさ $g$ の群を大きさ $s$ の網で捕まえるたびに、$s - g$ の空間を無駄にします。網の初期の大きさは自由で、大きさを $K$ 回変更できます $(1 \leq K < N)$。

すべての群を捕まえた後の無駄な空間の合計の最小値を Bessie に教えてください。

入力

最初の行は $N$ と $K$ を含みます。2 行目は $N$ 個の整数 $a_1,\dots,a_N$ を含み、$a_i$（$0 \leq a_i \leq 10^6$）は第 $i$ 群のヘビの数です。

出力

すべてのヘビを捕まえた後の無駄な空間の合計の最小値を表す整数を出力してください。

入出力例

入力 1

6 2
7 9 8 2 3 2

出力 1

3

注記

網の初期の大きさは 7 です。最初の群の後で大きさを 9 に変え、第 4 群まで保ち、そこで 3 に変えます。無駄な空間の合計は $(7-7) + (9-9) + (9-8) + (3-2) + (3-3) + (3-2) = 3.$ です。

問題作成者：Patrick Zhang