eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Проходження коридору

Проходження коридору

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Як ми вже знаємо, у грі Петрика є коридор, розбитий на N ділянок. Припустимо, що кожна з ділянок покрита деякою кідькістю одиничнох плит. Персонаж у грі, яким керує гравець, знаходиться на початкук коридору перед першою ділянкою і може пройти по цій ділянці, витративши на це один хід. Якщо на ній була хоча б одна плита, то після проходження по ділянці одна плита з неї зчезає. Таким чином кількість плит зменшиться на 1. Якщо ж на ділянкі не було жлдної плити, то персонаж гине, відповідно гравець втрачає одне життя, після чого на цій ділянці з'являється K нових плит, а у гравця з'являється новий персонаж на початку коридору. Якщо гравець вдало пройшов ділянку і не загинув, то він опиняється перед наступною ділянкою, яку він може пройти, якщо на ній єь хоча б одна плита, або загинути, якщо плит немає. У довільному випадку потрібно один хід. Дозволяється лише рух вперед. Вважається, що гравець пройшол коридор, якщо його персонаж у якийсь момент опиниться у кінці коридору, тобто пройде останню ділянку і не загине на ній. Допоможіть гравцю взнати, скільки потрібно життів і ходів для проходження коридору.

Вхідні дані

У першому рядку задано два цілих числа N і K (1N10000, 1K100) – довжина коридору і кількість плит на ділянці, що з'являютья післе гибелі персонажу. У другому рядку записано N цілих чисел, кожне з яких визначає кількість плит, якими покритн на початку відповідну ділянку. Ці числа можуть приймати значення відт 0 до K включно.

Вихідні дані

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

Приклад

Вхідні дані #1
3 3
2 2 2
Вихідні дані #1
0 3
Автор Антон Луньов
Джерело Зимова Школа, Харків 2011, День 6