問題文

長さ N の非負整数列 A = (A_1, A_2, ..., A_N) が与えられます。 あなたは以下の操作を 0 回以上 K 回以下行うことができます。

• 1 \leq i \leq N を満たす整数 i を一つ選び、A_i を 0 に変更する。

長さ N の整数列 B = (B_1, B_2, ..., B_N) を、 \displaystyle B_i = \sum_{j=1}^{i} A_j で定義します。 最終的な \displaystyle\sum_{i=1}^{N} B_i として考えられる最小値を求めてください。

制約

• 1 \leq K \leq N \leq 3 \times 10^5
• 0 \leq A_i \leq 10^7
• 入力はすべて整数

入力例 1

5 2
1 1 3 2 9

出力例 1

13

i = 3, 5 として操作を行ったとき A = (1, 1, 0, 2, 0) , B = (1, 2, 2, 4, 4) となり、B の総和は 13 になります。
どのように操作を行っても B の総和を 12 以下とすることはできないため、答えは 13 となります。

入力例 2

4 1
6 0 2 6

出力例 2

10

入力例 3

3 3
2 3 8

出力例 3

0