Капли
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

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

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

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

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

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

Первая строка входных данных содержит три натуральных числа n, m и k — количество капель, периодичность очистки трубы и имеющееся у героев время для сбора топлива, соответственно (1 ≤ n ≤ 105, 1 ≤ k ≤ 109, 0 ≤ t ≤ 109).

Во второй строке находятся n целых чисел pi, задающих периодичность падения каждой капли (1 ≤ pi ≤ 109).

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

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

Пример

Входные данные
3 5 17
1 2 3
Выходные данные
27