Задача A. Gorn ≡

Условие

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

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 10⁴

1 ≤ D ≤ 10⁵

1 ≤ K ≤ 10³

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

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

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

4 1 1
1 2 3 4

8