Fetching Water

Background

Special for beginners, ^_^

Problem Description

There is a water room in the school. It is equipped with a total of $m$ taps for students to fetch water, and each tap supplies water at the same rate of $1$ unit per second.

Now there are $n$ students about to fetch water, and their initial order has already been fixed. The students are numbered from $1$ to $n$ in this order, and the amount of water that student $i$ needs to fetch is $w_i$. When water fetching starts, students $1$ to $m$ each occupy one tap and turn on their taps simultaneously. When some student $j$ finishes fetching the required amount $w_j$, the next waiting student $k$ immediately takes over student $j$'s position and starts fetching water. This switch happens instantly, with no water wasted: if student $j$ finishes at the end of second $x$, student $k$ starts immediately at second $x+1$. If the current number of students fetching water, $n'$, is less than $m$, only $n'$ taps supply water and the other $m-n'$ taps are turned off.

Given the amounts $w_i$ of the $n$ students, according to the rules above, find how many seconds are needed for all students to finish fetching water.

Input Format

The first line contains two integers $n$ and $m$, separated by a space, denoting the number of students and the number of taps respectively.

The second line contains $n$ integers $w_1, w_2, \dots, w_n$, separated by spaces, where $w_i$ is the amount of water needed by student $i$.

Output Format

Output a single line with one integer: the total time needed to fetch water.

Sample Input 1

5 3
4 4 1 2 1

Sample Output 1

4

Hint

In the $1$-st second, $3$ people fetch water. At the end of the $1$-st second, students $1, 2, 3$ have each fetched $1$ unit; student $3$ finishes, and student $4$ takes over student $3$'s position.

In the $2$-nd second, $3$ people fetch water. At the end of the $2$-nd second, students $1, 2$ have each fetched $2$ units, and student $4$ has fetched $1$ unit.

In the $3$-rd second, $3$ people fetch water. At the end of the $3$-rd second, students $1, 2$ have each fetched $3$ units, and student $4$ has fetched $2$ units. Student $4$ finishes, and student $5$ takes over student $4$'s position.

In the $4$-th second, $3$ people fetch water. At the end of the $4$-th second, students $1, 2$ have each fetched $4$ units, and student $5$ has fetched $1$ unit. Students $1, 2, 5$ finish, meaning everyone has finished fetching water.

The total time needed to fetch water is $4$ seconds.

8 4
23 71 87 32 70 93 80 76

163

Constraints

1s, 1024KiB for each test case.