시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB59484382.692%

문제

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

После долгих блужданий по измерению, путешественники обнаружили, что нет там никаких ключей, и топливо стекает расположенными в ряд $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$).

출력

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

예제 입력 1

3 5 17
1 2 3

예제 출력 1

27