B. Ваня и кухонный комбайн
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Ваня измельчает картофель в вертикальном кухонном комбайне. В любой момент времени в комбайне помещается количество картофеля высоты не более h, при этом комбайн измельчает k сантиметров картофеля за секунду. Если картофеля в комбайне меньше k сантиметров, то за данную секунду комбайн измельчает весь оставшийся в нём картофель.

У Вани есть n картофелин, высота i-й из которых равна ai. Он поочередно засовывает в комбайн картофелины, начиная с картофелины номер 1 и заканчивая картофелиной номер n. Формально, каждую секунду происходит следующее:

  1. Если у Вани ещё остались картофелины, то он последовательно засовывает их в комбайн, пока там не кончится место.
  2. Комбайн измельчает k сантиметров картофеля (или просто всё, что есть в комбайне).

По имеющейся информации о параметрах комбайна и картофелин вычислите, за какое время весь картофель будет измельчён.

Входные данные

В первой строке входных данных находятся числа n, h и k (1 ≤ n ≤ 100 000, 1 ≤ k ≤ h ≤ 109) — количество картофелин, высота комбайна и количество картофеля, измельчаемое за одну секунду, соответственно.

Во второй строке записаны n целых чисел ai (1 ≤ ai ≤ h) — высоты картофелин.

Выходные данные

Выведите одно целое число — количество секунд, которые потребуются на измельчение всего имеющегося картофеля.

Примеры
Входные данные
5 6 3
5 4 3 2 1
Выходные данные
5
Входные данные
5 6 3
5 5 5 5 5
Выходные данные
10
Входные данные
5 6 3
1 2 1 1 1
Выходные данные
2
Примечание

Рассмотрим первый пример.

  1. Сначала Ваня засовывает в комбайн картофелину высотой 5. Через одну секунду в комбайне остаётся картофель высотой 2.
  2. Теперь Ваня засовывает картофелину высотой 4, и через секунду там остаётся количество картофеля высоты 3.
  3. Ваня засовывает картофель высотой 3, через секунду там снова столб картофеля высотой 3.
  4. Ваня засовывает картофелины высотой 2 и 1, через секунду опять остаётся количество картофеля высоты 3.
  5. На этой секунде комбайн измельчает весь оставшийся картофель и завершает свою работу.

Во втором примере Ваня засовывает в комбайн картофелину высотой 5 и ждёт две секунды, чтобы она полностью измельчилась. Аналогично для 4 следующих картофелин. Итого потребуется 2·5 = 10 секунд.

В третьем примере Ваня сразу засовывает в комбайн весь имеющийся картофель и ждёт 2 секунды.