Franklin está jugando al último videojuego de acción cronometrada de moda y se enfrenta a un "boss rush": un agotador desafío donde debe derrotar a $N$ monstruos (los jefes) para sobrevivir. Su única habilidad, el bloqueo (parry), es extremadamente poderosa pero muy difícil de usar.

Cada jefe ataca a Franklin una vez cada $d$ segundos; sin embargo, los jefes tienen su propio retraso inicial (starting delay) antes de comenzar su secuencia de ataques, de modo que los ataques de los jefes están escalonados. Más específicamente, si $f_i$ es el retraso inicial del $i$-ésimo jefe, entonces ese jefe atacará en los segundos $f_i, f_i + d, f_i + 2d, \dots$

Para defenderse, Franklin puede bloquear un ataque en el segundo exacto en que ocurre, derrotando instantáneamente al jefe y terminando con todos sus ataques posteriores. Franklin solo puede bloquear un ataque a la vez: si varios jefes lo atacan simultáneamente, puede bloquear como máximo uno de esos ataques.

Además, después de bloquear un ataque, Franklin queda agotado y no puede volver a bloquear durante los siguientes $w$ segundos. Formalmente, si Franklin bloquea un ataque en el segundo $t$, el momento más temprano en el que Franklin podría bloquear otro ataque es en el segundo $t + w$.

Franklin tiene mucha salud y no le preocupan los ataques de los jefes contra él, pero le gustaría terminar la pelea lo más rápido posible. Calcule la cantidad mínima de tiempo que le tomaría a Franklin derrotar a los $N$ jefes si bloquea de manera óptima.

Entrada

La primera línea de la entrada contiene tres enteros separados por espacios $N$ ($1 \le N \le 3 \cdot 10^5$), $w$ ($1 \le w \le 10^9$) y $d$ ($1 \le d \le 10^9$), donde $N$ es el número de jefes, $w$ es el número de segundos que Franklin debe esperar después de bloquear antes de poder bloquear de nuevo, y $d$ es el número de segundos entre dos ataques del mismo jefe.

La siguiente línea de la entrada contiene $N$ enteros separados por espacios $f_i$ ($0 \le f_i < d$), el retraso inicial de cada jefe en segundos.

Salida

Imprima el número de segundos que le toma a Franklin derrotar a los $N$ jefes si bloquea de manera óptima.

Nota

La explicación del primer ejemplo es la siguiente: el primer jefe ataca a Franklin en el segundo 2; Franklin podría bloquear el ataque pero elige esperar y, en su lugar, bloquear el ataque del segundo jefe en el segundo 3. Ahora está agotado y no puede volver a bloquear antes del segundo 7.

El tercer jefe ataca a Franklin en el segundo 8 y Franklin bloquea el ataque. Queda agotado de nuevo y no puede bloquear hasta el segundo 12: justo a tiempo para bloquear el segundo ataque del primer jefe, lo cual termina la pelea.

Ejemplos

Entrada 1

3 4 10
2 3 8

Salida 1

12

Entrada 2

3 4 10
2 3 9

Salida 2

13