Problem Statement

You are given positive integers $N, K$ and an integer sequence $A = (A _ 1, A _ 2, \ldots, A _ N)$ of length $N$.

Suisen's current satisfaction is $0$. He will now perform the following for $i = 1, 2, \ldots, K$, in this order.

• Let $\vert A\vert$ be the length of the sequence $A$.

  • If $\vert A\vert = 0$: Suisen's satisfaction becomes $-10 ^ {100}$.

  • If $\vert A\vert \geq 1$: choose an integer $p$ satisfying $1\leq p\leq \vert A\vert$ and remove the first $p$ elements of $A$. Letting $S$ be the sum of the elements removed, Suisen's satisfaction increases by $S\times i$.

    For example, if $p=2$ is chosen for $A=(-3,2,1)$, the first $2$ elements $-3,2$ are removed, resulting in $A = (1)$. The sum of the elements removed is $(-3)+2=-1$, so Suisen's satisfaction increases by $(-1)\times i$.

Find the maximum possible value of Suisen's satisfaction after all the operations are finished.

Input

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

• All input values are integers.
• $1\leq K \leq N\leq 5\times 10 ^ 5$
• $\vert A _ i \vert \leq 10 ^ 7$

Output

Print the answer on $1$ line. End the output with a newline.

Sample

5 3
3 2 0 1 -1

10

5 1
-5 1 -4 3 4

-1