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