P6568 [NOI Online #3 Senior] Water Jugs

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.

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$.

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

#### 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