Description

There is a water room in the school, equipped with a total of m faucets for students to fetch water. Each faucet provides an equal flow rate of 1 unit per second.

Now, n students are preparing to fetch water, and their initial order for fetching water has already been determined. These students are numbered from 1 to n according to their fetching order, and the i-th student's required water amount is wi. At the start of fetching water, the first m students occupy one faucet each and begin fetching water simultaneously. When any student j completes their required water amount wj, the next student k waiting in line immediately takes over student j's position to start fetching water. This replacement process happens instantaneously without any water wastage. That is, if student j finishes fetching water at the end of the x-th second, student k will start fetching water at the beginning of the (x+1)-th second. If the current number of students fetching water n' is less than m, only n' faucets will be in use, and the remaining m - n' faucets will be closed.

Given the water amounts for the n students and following the above fetching rules, determine how many seconds are required 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, respectively.
• The second line contains n integers w1, w2, ..., wn, separated by spaces, where wi represents the water amount required by the i-th student.

Output Format

The output consists of a single integer, representing the total time required for all students to finish fetching water.

5 3
4 4 1 2 1

4

8 4
23 71 87 32 70 93 80 76

163

Hint

Explanation of Sample Input and Output 1:

• At the 1st second, 3 people are filling water. By the end of the 1st second, students 1, 2, and 3 have each received 1 unit of water. Student 3 finishes filling, and student 4 takes over for student 3 to start filling.
• At the 2nd second, 3 people are filling water. By the end of the 2nd second, students 1 and 2 have each received 2 units of water, and student 4 has received 1 unit.
• At the 3rd second, 3 people are filling water. By the end of the 3rd second, students 1 and 2 have each received 3 units of water, and student 4 has received 2 units. Student 4 finishes filling, and student 5 takes over for student 4 to start filling.
• At the 4th second, 3 people are filling water. By the end of the 4th second, students 1 and 2 have each received 4 units of water, and student 5 has received 1 unit. Students 1, 2, and 5 finish filling, meaning all students have completed the task.
• The total filling time is 4 seconds.