Maximum Water Collection

You are given n water jugs of infinite capacity, numbered from 1 to n. Initially, the i-th jug contains \(A_i\) units of water. You are allowed to perform at most \(k\) operations. In each operation, you choose an index \(x\) with \(1 \le x \le n-1\) and pour all the water from jug \(x\) into jug \(x+1\). After performing at most \(k\) operations, you may choose exactly one jug and drink all the water contained in it. Your task is to determine the maximum number of water units you can drink.

Note: To move the water from jug \(i\) to jug \(j\) (where \(i < j\)), you need to perform \(j - i\) pouring operations. Therefore, if you want to consolidate water from a contiguous segment into jug \(j\), you can only include jugs \(i\) if \(j - i \leq k\). In other words, the maximum water in jug \(j\) you can obtain is:

[ \text{water}(j)=\sum_{i=\max(1,j-k)}^{j}A_i. ]

Your answer is the maximum value of \(\text{water}(j)\) over all \(j=1,2,\ldots, n\).

inputFormat

The first line contains two integers \(n\) and \(k\) separated by a space, where \(n\) is the number of water jugs and \(k\) is the maximum number of pouring operations allowed.

The second line contains \(n\) integers \(A_1, A_2, \ldots, A_n\), where \(A_i\) represents the amount of water in the \(i\)-th jug.

outputFormat

Output a single integer — the maximum number of water units that can be obtained from one jug after performing at most \(k\) operations.

sample

5 2
3 1 4 1 5

10