A. Будильники
Ограничение времени
2 секунды
Ограничение памяти
256Mb
Ввод
стандартный ввод или input.txt
Вывод
стандартный вывод или output.txt
Работа в большинстве IT-компаний имеет много преимуществ: нет дресс-кода, можно иногда поработать удалённо, классные и умные коллеги и, конечно же, свободный график! Однако свободный график и возможность работать удалённо требуют большой силы воли.
Программист Алексей любит работать по ночам и не любит приходить на работу поздно. Чтобы точно проснуться с утра, Алексей каждый вечер заводит N будильников на своём телефоне. Каждый будильник устроен таким образом, что он звонит каждые X минут с того момента времени, на который его завели. Например, если будильник был заведён на момент времени ti, то он будет звонить в моменты времени ti, ti+X, ti+2⋅X и так далее. При этом если какие-то два будильника начинают звонить в один момент времени, то отображается только один из них.
Известно, что прежде чем проснуться, Алексей каждое утро слушает ровно K будильников, после чего просыпается. Определите момент времени, когда Алексей проснётся.
Формат ввода
Первая строка содержит три целых числа N, X и K (1≤N≤105, 1≤X,K≤109) — количество будильников, периодичность звонков и количество будильников, которое нужно отключить, чтобы Алексей проснулся.
Вторая строка содержит N целых чисел t1, t2, …, tN (1≤ti≤109) — моменты времени на которые были заведены будильники.
Формат вывода
Выведите одно число — момент времени, когда Алексей проснётся.
Пример 1
Ввод
Вывод
6 5 10
1 2 3 4 5 6
10
Пример 2
Ввод
Вывод
5 7 12
5 22 17 13 8
27
Примечания
Во втором примере заведено 5 будильников с периодичностью звонков 7. Например, первый будильник будет звонить в моменты времени 5, 12, 19, 26, 33, и т. д. Если рассмотреть все будильники одновременно, то они будут звонить в следующие моменты времени: 5, 8, 12, 13, 15, 17, 19, 20, 22 (2-й и 5-й будильники одновременно), 24, 26, 27, 29, … На 12-й по счёту звонок Алексей должен проснуться, чему соответствует момент времени 27.