Franklin joue au dernier jeu vidéo d'action chronométré à la mode et fait face à un « boss rush » : un défi éprouvant où il doit vaincre $N$ monstres (les boss) pour survivre. Sa seule capacité, la parade, est extrêmement puissante mais très difficile à utiliser.
Chaque boss attaque Franklin une fois toutes les $d$ secondes ; cependant, les boss ont leur propre délai de démarrage avant de commencer leur séquence d'attaques, de sorte que les attaques des boss sont décalées. Plus précisément, si $f_i$ est le délai de démarrage du $i$-ième boss, alors ce boss attaquera aux secondes $f_i, f_i + d, f_i + 2d, \dots$
Pour se défendre, Franklin peut parer une attaque à la seconde exacte où elle se produit, vainquant instantanément le boss et mettant fin à toutes ses attaques ultérieures. Franklin ne peut parer qu'une seule attaque à la fois : si plusieurs boss l'attaquent simultanément, il peut parer au plus une de ces attaques.
De plus, après avoir paré une attaque, Franklin est essoufflé et ne peut plus parer pendant les $w$ secondes suivantes. Formellement, si Franklin pare une attaque à la seconde $t$, le moment le plus tôt où Franklin peut parer une autre attaque est à la seconde $t + w$.
Franklin a beaucoup de points de vie et ne se soucie pas des attaques des boss contre lui, mais il souhaite terminer le combat le plus rapidement possible. Calculez le temps minimum nécessaire pour que Franklin vainque les $N$ boss s'il pare de manière optimale.
Entrée
La première ligne de l'entrée contient trois entiers séparés par des espaces $N$ ($1 \le N \le 3 \cdot 10^5$), $w$ ($1 \le w \le 10^9$) et $d$ ($1 \le d \le 10^9$), où $N$ est le nombre de boss, $w$ est le nombre de secondes que Franklin doit attendre après une parade avant de pouvoir parer à nouveau, et $d$ est le nombre de secondes entre deux attaques du même boss.
La ligne suivante contient $N$ entiers séparés par des espaces $f_i$ ($0 \le f_i < d$), le délai de démarrage de chaque boss en secondes.
Sortie
Affichez le nombre de secondes nécessaires pour que Franklin vainque les $N$ boss s'il pare de manière optimale.
Exemples
Exemples 1
3 4 10 2 3 8
12
Remarque 1
Le premier boss attaque Franklin à la seconde 2 ; Franklin pourrait parer l'attaque mais choisit de patienter et de parer plutôt l'attaque du deuxième boss à la seconde 3. Il est alors essoufflé et ne peut plus parer avant la seconde 7.
Le troisième boss attaque Franklin à la seconde 8 et Franklin pare l'attaque. Il est à nouveau essoufflé et ne peut plus parer avant la seconde 12 : juste à temps pour parer la deuxième attaque du premier boss, ce qui met fin au combat.
Exemples 2
3 4 10 2 3 9
13