Problem Description

There is a water room in the school with a total of $m$ faucets available for students to get water. Each faucet provides the same amount of water per second, which is $1$.

Now, there are $n$ students ready to get water, and their initial order of getting water is determined. These students are numbered from $1$ to $n$ according to their order of getting water, where the $i$-th student's water requirement is $w_i$. At the start of water dispensing, students $1$ to $m$ each occupy a faucet and start getting water simultaneously. When a student $j$ finishes their water requirement $w_j$, the next student $k$ in line immediately takes over $j$'s position to start getting water. This replacement process happens instantly without any waste of water. That is, if student $j$ finishes at the $x$-th second, student $k$ starts immediately at the $x+1$-th second. If the number of students currently getting water $n'$ is less than $m$, then only $n'$ faucets are in use, and the remaining $m - n'$ faucets are closed.

Given the water requirements of $n$ students, according to the above rules, calculate the total number of seconds required for all students to finish getting 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, respectively.

The second line contains $n$ integers $w_1, w_2, \ldots, w_n$, each separated by a space, where $w_i$ represents the water requirement of the $i$-th student.

Output Format

An integer representing the total time required for all students to finish getting water.

Sample Input and Output

Sample Input #1

5 3
4 4 1 2 1

Sample Output #1

4

Sample Input #2

8 4
23 71 87 32 70 93 80 76

Sample Output #2

163

Notes

Sample #1 Explanation:

• At the 1st second, 3 students are getting water. At the end of the 1st second, students 1, 2, and 3 each have received 1 unit of water. Student 3 finishes, and student 4 takes over.
• At the 2nd second, 3 students are getting water. At the end of the 2nd second, students 1 and 2 each have received 2 units of water, and student 4 has received 1 unit.
• At the 3rd second, 3 students are getting water. At the end of the 3rd second, students 1 and 2 each have received 3 units of water, and student 4 has received 2 units. Student 4 finishes, and student 5 takes over.
• At the 4th second, 3 students are getting water. At the end of the 4th second, students 1 and 2 each have received 4 units of water, and student 5 has received 1 unit. Students 1, 2, and 5 finish, totaling 4 seconds for everyone to complete getting water.

Data Range:

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

$1 \le w_i \le 100$.

NOIP2010 Junior Group Problem 2

见题面 Input 部分

见题面 Output 部分