Description

There is a water room in the school with a total of $m$ faucets that students can use. Each faucet supplies water at an equal rate of $1$ unit per second.

Now $n$ students are preparing to fetch water, and their initial order is fixed. Number the students from $1$ to $n$ according to this order, and let the required amount for student $i$ be $w_i$. At the start, students $1$ through $m$ each occupy one faucet and start fetching water simultaneously. When some student $j$ finishes their required amount $w_j$, the next student $k$ in the queue immediately takes $j$’s place and starts fetching water. This handover is instantaneous, and no water is wasted. Specifically, if student $j$ finishes at the end of second $x$, then student $k$ starts at second $x+1$. If the current number of students fetching water is $n' < m$, then only $n'$ faucets supply water, and the remaining $m - n'$ faucets are closed.

Given the required amounts for the $n$ students and following the rules above, determine how many seconds it takes for all students to finish fetching water.

Input Format

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

The second line contains $n$ integers $w_1,w_2,\ldots,w_n$, separated by single spaces, where $w_i$ is the required amount for student $i$.

Output Format

Output a single integer representing the total time required.

5 3
4 4 1 2 1

4

8 4
23 71 87 32 70 93 80 76

163

Hint

[Sample I/O #1 Explanation]

In the 1st second, 3 students are fetching water. At the end of the 1st second, students 1, 2, and 3 have each fetched 1 unit. Student 3 finishes, and student 4 takes student 3’s place to start fetching water.

In the 2nd second, 3 students are fetching water. At the end of the 2nd second, students 1 and 2 have each fetched 2 units, and student 4 has fetched 1 unit.

In the 3rd second, 3 students are fetching water. At the end of the 3rd second, students 1 and 2 have each fetched 3 units, and student 4 has fetched 2 units. Student 4 finishes, and student 5 takes student 4’s place to start fetching water.

In the 4th second, 3 students are fetching water. At the end of the 4th second, students 1 and 2 have each fetched 4 units, and student 5 has fetched 1 unit. Students 1, 2, and 5 finish, so the total time for everyone to finish is 4 seconds.

Constraints

$1 \le n \le 10^4$, $1 \le m \le 100$, $m \le n$;

$1 \le w_i \le 100$.

NOIP 2010 Junior Problem 2.

Translated by ChatGPT 5