Біг#10152

Біг

1 секунда

128 мегабайтів

Легка

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

Загальна відстань, яку може пробігти Бессі, залежить від її коефіцієнта втоми, який спочатку дорівнює $0$ . Якщо Бессі біжить протягом хвилини $i$ , вона пробігає відстань $d_{i}$ d_i, а її коефіцієнт втоми збільшується на $1$ . Коефіцієнт втоми ніколи не може перевищувати $m$ .

Якщо Бессі відпочиває, її коефіцієнт втоми зменшується на $1$ , але не може стати від'ємним. Бессі може знову почати бігти лише тоді, коли її коефіцієнт втоми досягне $0$ . У цей момент вона може обрати: або бігти, або продовжити відпочивати.

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

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

Вхідні дані

У першому рядку знаходяться два цілих числа $n (1 \leq n \leq 1 0^{4})$ n~(1 \le n \le 10^4) та $m (1 \leq m \leq 500)$ m~(1 \le m \le 500).

Наступні $n$ рядків містять цілі числа $d_{1}, d_{2}, \dots, d_{n} (1 \leq d_{i} \leq 1000)$ d_1, d_2, \ldots, d_n~(1 \le d_i \le 1000), де $d_{i}$ d_i — відстань, яку Бессі пробігає, якщо вирішує бігти протягом хвилини $i$ .

Вихідні дані

Виведіть одне ціле число: максимальну сумарну відстань, яку може пробігти Бессі, дотримуючись усіх заданих правил.

Приклади

Приклад 1