Франклин играет в новейшую модную видеоигру с элементами тайминга и столкнулся с «босс-рашем»: сложным испытанием, в котором он должен победить $N$ монстров (боссов), чтобы выжить. Его единственная способность, парирование, невероятно мощна, но очень сложна в использовании.

Каждый босс атакует Франклина один раз в $d$ секунд; однако у боссов есть собственная начальная задержка перед началом серии атак, поэтому атаки боссов распределены во времени. Более конкретно, если $f_i$ — это начальная задержка $i$-го босса, то этот босс будет атаковать в моменты времени $f_i, f_i + d, f_i + 2d, \dots$

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

Более того, после парирования атаки Франклин выдыхается и не может парировать снова в течение следующих $w$ секунд. Формально, если Франклин парирует атаку в момент времени $t$, самый ранний момент, когда Франклин может парировать следующую атаку, — это момент $t + w$.

У Франклина много здоровья, и он не беспокоится об атаках боссов, но он хочет закончить бой как можно быстрее. Вычислите минимальное время, которое потребуется Франклину, чтобы победить всех $N$ боссов, если он будет парировать оптимально.

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

Первая строка входных данных содержит три целых числа, разделенных пробелами: $N$ ($1 \le N \le 3 \cdot 10^5$), $w$ ($1 \le w \le 10^9$) и $d$ ($1 \le d \le 10^9$), где $N$ — количество боссов, $w$ — количество секунд, которое Франклин должен ждать после парирования, прежде чем снова сможет парировать, а $d$ — количество секунд между двумя атаками одного и того же босса.

Следующая строка содержит $N$ целых чисел, разделенных пробелами: $f_i$ ($0 \le f_i < d$), начальная задержка каждого босса в секундах.

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

Выведите количество секунд, которое потребуется Франклину, чтобы победить всех $N$ боссов при оптимальном парировании.

Примеры

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

3 4 10
2 3 8

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

12

Примечание

Первый босс атакует Франклина на 2-й секунде; Франклин мог бы парировать эту атаку, но решает подождать и вместо этого парирует атаку второго босса на 3-й секунде. Теперь он выдохся и не может парировать снова до 7-й секунды.

Третий босс атакует Франклина на 8-й секунде, и Франклин парирует эту атаку. Он снова выдыхается и не может парировать до 12-й секунды: как раз вовремя, чтобы парировать вторую атаку первого босса, что завершает бой.

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

3 4 10
2 3 9

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

13