28859번 - Капли 다국어

문제

Странствуя по загадочным измерениям, Рик обнаружил одно совершенно уникальное, где били ключи с редчайшим топливом, требующимся ему для конструирования нового изобретения. Чтобы отыскать эти ключи, Рик, естественно, решил отправиться туда вместе с внуком.

После долгих блужданий по измерению, путешественники обнаружили, что нет там никаких ключей, и топливо стекает расположенными в ряд $n$ маленькими каплями с горизонтально подвешенной в воздухе трубы.

Рик и Морти заметили, что каждая капля падает вниз с какой-то своей периодичностью, а именно --- каждые $p_i$ секунд, а также то, что каждые $k$ секунд внешняя поверхность трубы очищается и каждая капля начинает расти сначала, причем если капля готова упасть в момент очистки трубы, она падает, и только после этого происходит очистка.

У Рика и Морти есть расширяющаяся до произвольных размеров емкость для сбора жидкости, то есть они могут собрать каждую упавшую каплю, но на это у них есть всего $t$ секунд, после этого их могут заметить.

Помогите героям посчитать количество капель, которые они смогут собрать, если они подошли к трубе сразу после ее очистки и тут же приступили к сбору.

입력

Первая строка входных данных содержит три натуральных числа $n,ドル $m$ и $k$ --- количество капель, периодичность очистки трубы и имеющееся у героев время для сбора топлива, соответственно (1ドル \le n \le 10^5,ドル 1ドル \le k \le 10^9,ドル 0ドル \le t \le 10^9$).

Во второй строке находятся $n$ целых чисел $p_i,ドル задающих периодичность падения каждой капли (1ドル \le p_i \le 10^9$).

출력

Выведите одно число --- количество капель, которое упадет с трубы за имеющееся у Рика и Морти время.

제한

힌트