Franklin gra w najnowszą modną grę akcji i mierzy się z „boss rushem”: wymagającym wyzwaniem, w którym musi pokonać $N$ potworów (bossów), aby przetrwać. Jego jedyna umiejętność, parowanie, jest niezwykle potężna, ale bardzo trudna w użyciu.

Każdy boss atakuje Franklina raz na $d$ sekund; jednak bossowie mają własne opóźnienie początkowe, zanim rozpoczną swoją sekwencję ataków, dzięki czemu ataki bossów są rozłożone w czasie. Mówiąc dokładniej, jeśli $f_i$ jest opóźnieniem początkowym $i$-tego bossa, to boss ten zaatakuje w sekundach $f_i, f_i + d, f_i + 2d, \dots$

Aby się bronić, Franklin może sparować atak dokładnie w sekundzie, w której on następuje, natychmiast pokonując bossa i kończąc wszystkie jego kolejne ataki. Franklin może sparować tylko jeden atak naraz: jeśli wielu bossów atakuje go jednocześnie, może sparować co najwyżej jeden z tych ataków.

Co więcej, po sparowaniu ataku Franklin staje się zmęczony i nie może ponownie parować przez kolejne $w$ sekund. Formalnie, jeśli Franklin paruje atak w sekundzie $t$, najwcześniejszy moment, w którym Franklin może sparować kolejny atak, to sekunda $t + w$.

Franklin ma dużo zdrowia i nie przejmuje się atakami bossów, ale chciałby zakończyć walkę tak szybko, jak to możliwe. Oblicz minimalny czas, jaki zajmie Franklinowi pokonanie wszystkich $N$ bossów, jeśli paruje optymalnie.

Wejście

Pierwsza linia wejścia zawiera trzy liczby całkowite oddzielone spacjami $N$ ($1 \le N \le 3 \cdot 10^5$), $w$ ($1 \le w \le 10^9$) oraz $d$ ($1 \le d \le 10^9$), gdzie $N$ to liczba bossów, $w$ to liczba sekund, które Franklin musi odczekać po sparowaniu przed kolejnym parowaniem, a $d$ to liczba sekund między dwoma atakami tego samego bossa.

Druga linia wejścia zawiera $N$ liczb całkowitych oddzielonych spacjami $f_i$ ($0 \le f_i < d$), oznaczających opóźnienie początkowe każdego bossa w sekundach.

Wyjście

Wypisz liczbę sekund, które zajmie Franklinowi pokonanie wszystkich $N$ bossów, jeśli paruje optymalnie.

Uwagi

Wyjaśnienie dla pierwszego przykładu: Pierwszy boss atakuje Franklina w sekundzie 2; Franklin mógłby sparować ten atak, ale decyduje się poczekać i zamiast tego paruje atak drugiego bossa w sekundzie 3. Jest teraz zmęczony i nie może ponownie parować przed sekundą 7.

Trzeci boss atakuje Franklina w sekundzie 8 i Franklin paruje ten atak. Jest ponownie zmęczony i nie może parować do sekundy 12: w samą porę, aby sparować drugi atak pierwszego bossa, co kończy walkę.

Przykład

Wejście 1

3 4 10
2 3 8

Wyjście 1

12

Wejście 2

3 4 10
2 3 9

Wyjście 2

13