Задача A. Gorn

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:256 Мб
Максимальный балл:100  

Условие

Вильгельм играет в игру Gorn в виртуальной реальности, сражаясь с N гладиаторами на арене. Он имеет при себе лук и бесконечное число стрел и никогда не промахивается по врагам.

Когда Вильгельм в первый раз попадает по вражескому гладиатору, он наносит ему D единиц урона, гладиатор при этом теряет D единиц здоровья. При каждом следующем попадании по этому гладиатору урон увеличивается на K единиц из-за ослабевающей брони гладиатора. При попадании по новому гладиатору урон также начинается с D и увеличивается с каждым попаданием. Гладиатор погибает, когда количество его здоровья достигает нуля или становится отрицательным.

Каково наименьшее количество стрел, которые должен потратить Вильгельм, чтобы убить всех гладиаторов?

Формат входного файла

Первая строка входного файла содержит целые числа N, D и K. В следующей строке содержится N целых чисел hi — количество здоровья у вражеских гладиаторов.

Формат выходного файла

Программа должна вывести одно целое число — количество стрел, которые необходимо потратить.

Ограничения

1 ≤ N ≤ 104

1 ≤ D≤ 105

1 ≤ K ≤ 103

Описание подзадач и системы оценивания

Баллы за 1 подзадачу начисляются только в случае, если все тесты для этой подзадачи успешно пройдены. Баллы за подзадачу 2 начисляются за каждый пройденный тест, если тесты необходимых подзадач пройдены.

Подзадача Баллы Дополнительные ограничения Необходимые подзадачи
hi
1401 ≤ hi ≤ 102
2601 ≤ hi ≤ 10151

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
4 1 1
1 2 3 4
8

0.063s 0.010s 13