問題文

正整数 $N, K$ および長さ $N$ の整数列 $A = (A _ 1, A _ 2, \ldots, A _ N)$ が与えられます。

suisen 君の現在の満足度は $0$ です。suisen 君はこれから $i = 1, 2, \ldots, K$ の順に次を行います。

• 数列 $A$ の長さを $\vert A\vert$ とする。

  • $\vert A\vert = 0$ の場合: suisen 君の満足度は $-10 ^ {100}$ となる。

  • $\vert A\vert \geq 1$ の場合: $1\leq p\leq \vert A\vert$ を満たす整数 $p$ を選んで、$A$ の先頭から $p$ 個の要素を取り除く。このとき取り除いた要素の総和を $S$ として、suisen 君の満足度は $S\times i$ だけ増加する。

    例えば $A=(-3,2,1)$ に対して $p=2$ を選択すると先頭から $2$ つの要素 $-3,2$ が取り除かれ、$A = (1)$ となります。このとき取り除いた要素の総和は $(-3)+2=-1$ なので、suisen 君の満足度は $(-1)\times i$ だけ増加します。

全ての操作を終えた後の suisen 君の満足度の最大値を求めてください。

入力

$N\ K$
$A _ 1\ A _ 2 \ \cdots \ A _ N$

• 入力は全て整数で与えられる。
• $1\leq K \leq N\leq 5\times 10 ^ 5$
• $\vert A _ i \vert \leq 10 ^ 7$

出力

答えを $1$ 行に出力してください。最後に改行してください。

サンプル

5 3
3 2 0 1 -1

10

5 1
-5 1 -4 3 4

-1