Problem Description

There are $n$ water jugs with infinite capacity, numbered from $1$ to $n$. Initially, jug $i$ contains $A_i$ units of water.

You can perform at most $k$ operations. In each operation, you need to choose an index $x$ such that $1 \le x \le n-1$, and then pour all the water from jug $x$ into jug $x+1$.

In the end, you may choose exactly one jug and drink all the water in it. Now, please find the maximum number of units of water you can drink.

Input Format

The first line contains a positive integer $n$, indicating the number of water jugs.

The second line contains a non-negative integer $k$, indicating the upper limit on the number of operations.

The third line contains $n$ non-negative integers, separated by spaces, representing the initial amounts of water $A_1$, $A_2$, $\cdots$, $A_n$.

Output Format

One line with a single non-negative integer, indicating the answer.

10
5
890 965 256 419 296 987 45 676 976 742

3813

Hint

Constraints

• For $10\%$ of the testdata, it is guaranteed that $n \le 10$.
• For $30\%$ of the testdata, it is guaranteed that $n \le 100$.
• For $50\%$ of the testdata, it is guaranteed that $n \le 10^3$.
• For $70\%$ of the testdata, it is guaranteed that $n \le 10^5$.
• For $100\%$ of the testdata, it is guaranteed that $1 \le n \le 10^6$, $0 \le k \le n-1$, and $0 \le A_i \le 10^3$.

Translated by ChatGPT 5