Біг
Корови хочуть стати кращими спортсменами, тому Бессі біжить по дорожці рівно n хвилин. Кожну хвилину вона може або бігти, або відпочивати цілу хвилину.
Проте максимальну відстань, яку пробігає Бессі, залежить від її фактора виснаження, який начинається з 0. Якщо вона вирішила бігти в хвилину i, то пробіжить відстань d[i], а її коефіцієнт виснадження збільшиться на 1 (проте він ніколи не повинен перевищувати m). Якщо Бессі вирішить відпочити, то її фактор виснаження зменшиться на 1 за кожну хвилину відпочинку. Вона не може знову бігти, поки її фактор виснаження не досягне 0. В цей момент вона може вибрати що робити - бігти чи відпочивати.
В кінці n-ої хвилини тренування коефіцієнт виснаження Бессі повинен дорівнювати 0, інакше у неї не озалишиться енергії до кінця дня.
Знайдіть максимальну відстань, яку може пробігти Бессі.
Вхідні дані
Перший рядок містить два цілих числа n (1 ≤ n ≤ 10^4) і m (1 ≤ m ≤ 500). Наступні n рядків містить ціліе числа d[1], d[2], ..., d[n] (1 ≤ d[i] ≤ 1000).
Виходни дані
Виведіть єдине ціле число - найбільшу відстань, яку Бессі може пробігти при виконанні умов.