Description

Franklin is playing the latest trendy timed-action video game and is facing a boss rush: a trying gauntlet where he must defeat $N$ monsters (the bosses) to survive. His only ability, $\textit{parry}$, is extremely powerful but very difficult to use.

Each boss attacks Franklin once every $d$ seconds; however, the bosses have their own $\emph{starting delay}$ before they begin their sequence of attacks, so that the boss attacks are staggered. More specifically, if $f_i$ is the starting delay of the $i\text{th}$ boss, then that boss will attack at seconds

To defend himself, Franklin can parry an attack on the exact second it happens, instantly defeating the boss and ending all of its subsequent attacks. Franklin can only parry one attack at a time: if multiple bosses attack him simultaneously, he can parry at most one of those attacks.

Moreover, after parrying an attack Franklin becomes winded and cannot parry again during the next $w$ seconds. Formally, if Franklin parries an attack at second $t$, the earliest moment that Franklin could parry another attack is at second $t+w$.

Franklin has plenty of health and is unconcerned about the attacks of the bosses against him, but he'd like to end the fight as quickly as possible. Compute the minimum amount of time it would take Franklin to defeat all $N$ bosses if he parries optimally.

Input Format

The first line of input contains three space-separated integers $N$ $(1 \leq N \leq 3\cdot 10^5)$, $w$ $(1 \leq w \leq 10^9)$, and $d$ $(1 \leq d \leq 10^9)$, where $N$ is the number of bosses, $w$ is the number of seconds Franklin must wait after parrying before parrying again, and $d$ is the number of seconds between two attacks by the same boss.

The next line of input contains $N$ space-separated integers $f_i$ $(0 \leq f_i < d)$, the starting delay of each boss in seconds.

Output Format

Print the number of seconds it takes Franklin to defeat all $N$ bosses if he parries optimally.

3 4 10
2 3 8

12

3 4 10
2 3 9

13

Hint

Explanation of Sample Input 1

The first boss attacks Franklin at second $2$; Franklin could parry the attack but chooses to bide his time and instead parry the attack of the second boss at second $3$. He is now winded and cannot parry again before second $7$.

The third boss attacks Franklin at second $8$ and Franklin parries the attack. He is winded again and cannot parry until second $12$: just in time to parry the first boss's second attack, which ends the fight.