Water Collection Process

In a school, there is a water room with \(m\) faucets, each providing water at a rate of \(1\) unit per second.

There are \(n\) students waiting in line. The students are numbered from \(1\) to \(n\) according to their order in line, and the \(i\)-th student requires \(w_i\) units of water. Initially, the first \(m\) students occupy the faucets and start collecting water simultaneously. When a student, say student \(j\), finishes collecting water exactly at the end of a second (i.e. after receiving exactly \(w_j\) units of water), the next student in the queue, say student \(k\), immediately starts collecting water from that faucet in the next second. This substitution is instantaneous and no water is wasted. If there are fewer than \(m\) students collecting water, only that many faucets are active while the others remain closed.

Your task is to determine the total number of seconds required for all the students to finish collecting water.

inputFormat

The first line contains two integers \(n\) and \(m\) (\(1 \le m \le n \le 10^5\)) -- the number of students and the number of faucets.

The second line contains \(n\) integers \(w_1, w_2, \dots, w_n\) (\(1 \le w_i \le 10^9\)) representing the amount of water each student requires.

outputFormat

Output a single integer representing the total number of seconds required for all students to finish collecting water.

sample

5 2
4 2 1 3 3

7