Корови хочуть стати кращими спортсменами, тому Бессі біжить по дорожці рівно n хвилин. Кожну хвилину вона може або бігти, або відпочивати цілу хвилину.

Проте максимальну відстань, яку пробігає Бессі, залежить від її фактора виснаження, який начинається з 0. Якщо вона вирішила бігти в хвилину i, то пробіжить відстань di, а її коефіцієнт виснадження збільшиться на 1 (проте він ніколи не повинен перевищувати m). Якщо Бессі вирішить відпочити, то її фактор виснаження зменшиться на 1 за кожну хвилину відпочинку. Вона не може знову бігти, поки її фактор виснаження не досягне 0. В цей момент вона може вибрати що робити - бігти чи відпочивати.

В кінці n-ої хвилини тренування коефіцієнт виснаження Бессі повинен дорівнювати 0, інакше у неї не озалишиться енергії до кінця дня.

Знайдіть максимальну відстань, яку може пробігти Бессі.

Вхідні дані

Перший рядок містить два цілих числа n (1 ≤ n ≤ 104) і m (1 ≤ m ≤ 500). Наступні n рядків містить ціліе числа d1, d2, ..., dn (1 ≤ di ≤ 1000).

Виходни дані

Виведіть єдине ціле число - найбільшу відстань, яку Бессі може пробігти при виконанні умов.