問題描述

　　學(xué)校里有一個水房，水房里一共裝有m 個龍頭可供同學(xué)們打開水，每個龍頭每秒鐘的 供水量相等，均為1。 現(xiàn)在有n 名同學(xué)準(zhǔn)備接水，他們的初始接水順序已經(jīng)確定。將這些同學(xué)按接水順序從1 到n 編號，i 號同學(xué)的接水量為wi。接水開始時，1 到m 號同學(xué)各占一個水龍頭，并同時打 開水龍頭接水。當(dāng)其中某名同學(xué)j 完成其接水量要求wj 后，下一名排隊等候接水的同學(xué)k 馬上接替j 同學(xué)的位置開始接水。這個換人的過程是瞬間完成的，且沒有任何水的浪費。即 j 同學(xué)第x 秒結(jié)束時完成接水，則k 同學(xué)第x+1 秒立刻開始接水。若當(dāng)前接水人數(shù)n’不足m， 則只有n’個龍頭供水，其它m?n’個龍頭關(guān)閉。 現(xiàn)在給出n 名同學(xué)的接水量，按照上述接水規(guī)則，問所有同學(xué)都接完水需要多少秒。

輸入格式

　　第1 行2 個整數(shù)n 和m，用一個空格隔開，分別表示接水人數(shù)和龍頭個數(shù)。 第2 行n 個整數(shù)w1、w2、……、wn，每兩個整數(shù)之間用一個空格隔開，wi 表示i 號同 學(xué)的接水量。

輸出格式

　　輸出只有一行，1 個整數(shù)，表示接水所需的總時間。

樣例輸入

5 3

4 4 1 2 1

樣例輸出

4

樣例輸入

8 4

23 71 87 32 70 93 80 76

樣例輸出

163

輸入輸出樣例 1 說明

　　第1 秒，3 人接水。第1 秒結(jié)束時，1、2、3 號同學(xué)每人的已接水量為1，3 號同學(xué)接完

　　水，4 號同學(xué)接替3 號同學(xué)開始接水。

　　第2 秒，3 人接水。第2 秒結(jié)束時，1、2 號同學(xué)每人的已接水量為2，4 號同學(xué)的已接

　　水量為1。

　　第3 秒，3 人接水。第3 秒結(jié)束時，1、2 號同學(xué)每人的已接水量為3，4 號同學(xué)的已接

　　水量為2。4 號同學(xué)接完水，5 號同學(xué)接替4 號同學(xué)開始接水。

　　第4 秒，3 人接水。第4 秒結(jié)束時，1、2 號同學(xué)每人的已接水量為4，5 號同學(xué)的已接

　　水量為1。1、2、5 號同學(xué)接完水，即所有人完成接水。

　　總接水時間為4 秒。

數(shù)據(jù)規(guī)模和約定

　　1 ≤ n ≤ 10000，1 ≤m≤ 100 且m≤ n；

　　1 ≤ wi ≤ 100。