問題文

長さ $N$ の整数列 $A=(A_1,A_2,\\dots,A_N)$ が与えられます。

長さ $M$ の $A$ の連続部分列 $B=(B_1,B_2,\\dots,B_M)$ に対する、$\\displaystyle \\sum_{i=1}^{M} i \\times B_i$ の最大値を求めてください。

注記

数列の連続部分列とは、数列の先頭から $0$ 個以上、末尾から $0$ 個以上の要素を削除して得られる列のことをいいます。

例えば $(2, 3)$ や $(1, 2, 3)$ は $(1, 2, 3, 4)$ の連続部分列ですが、$(1, 3)$ や $(3,2,1)$ は $(1, 2, 3, 4)$ の連続部分列ではありません。

制約

• $1 \\le M \\le N \\le 2 \\times 10^5$
• $\- 2 \\times 10^5 \\le A_i \\le 2 \\times 10^5$
• 入力は全て整数。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $A_1$ $A_2$ $\\dots$ $A_N$

出力

答えを出力せよ。

入力例 1

4 2
5 4 -1 8

出力例 1

15

$B=(A_3,A_4)$ とした場合、$\\displaystyle \\sum_{i=1}^{M} i \\times B_i = 1 \\times (-1) + 2 \\times 8 = 15$ となります。$16$ 以上の値を達成することはできないため、解は $15$ です。

$B=(A_1,A_4)$ などを選ぶことができないことに注意してください。

入力例 2

10 4
-3 1 -4 1 -5 9 -2 6 -5 3

出力例 2

31