This street is $L$ meters long, and currently William is at $x=0$, trying to reach his nest at $x=L$.

Along this street there are $N$ semaphores at positions $X_i$.

Along this street there are $N$ semaphores at positions $X[i]$.

All the traffic lights are synchronized: at $t=0$ the green triggers, and will stay green for $T$ seconds; at $t=T$ the red triggers, and will stay red for $T$ seconds; and then the cycle repeats.

Which is the least amount of time William needs to reach his nest?

h2. Date de intrare
The first line of the input file $police.in$ contains 4 integers: $N$ (the number of semaphores), $R$ (the number of semaphores William can skip), $T$ (the half-period of the semaphores), and $L$ (the length of the street).

The second line contains $N$ integers: the coordinates $X_i$.
 

The second line contains $N$ integers: the coordinates X[i].
 

h2. Date de ieşire
The output file $police.out$ contains a single line with an integer: the minimum time in seconds that will be needed to reach the nest.

h2. Restricţii
* $1 ≤ R ≤ N ≤ 10000$

* $N < L &le; 10^9$
* $X[i] < L$, for each semaphore
* $X[i] < X[i+1]$ for each $i$ from $0$ to $n-2$

* For tests worth $15$ more points, $R = 0$.
* For tests worth $15$ more points, $N ≤ 20$ and $L ≤ 1000$.
* For tests worth $25$ more points, $N, T ≤ 100$ and $L ≤ 1000$.
* For tests worth $15$ more points, $N ≤ 300$.
 

h2. Exemplu

h3. Explicaţie

In the \textbf{first sample case} there are 3 semaphores, of which 1 can be skipped. When William reaches the first semaphore he finds it green, so it will pass.

In the first sample case there are 3 semaphores, of which 1 can be skipped. When William reaches the first semaphore he finds it green, so it will pass.

Then at $t=5$ he reaches the second semaphore (at $x=5$), but it is red (since $t=3$).
He has two choices: wait 1 second that it becomes green, or skip the semaphore.

\begin{itemize}
    \item If he waits, he will start again at $t=6$, will reach the last semaphore (at $t=10$) and will skip it since it is red and he still has $1$ skip remaining.
    He reaches his nest at $t=11$.
 
    \item If he skips it, he will reach the last semaphore at $t=9$, but it is red (it just became red).
    There he has to wait 3 seconds that it becomes green again, leaving it at $t=12$.
    He reaches his nest at $t=13$.
\end{itemize}

If he waits, he will start again at $t=6$, will reach the last semaphore (at $t=10$) and will skip it since it is red and he still has $1$ skip remaining. He reaches his nest at $t=11$.
 
If he skips it, he will reach the last semaphore at $t=9$, but it is red (it just became red). There he has to wait 3 seconds that it becomes green again, leaving it at $t=12$. He reaches his nest at $t=13$.

Therefore, the best solution is to wait at the second semaphore and skip the last one, reaching the nest in 11 seconds.

In the \textbf{second sample case} there is only one semaphore.

In the second sample case there is only one semaphore.

When William reaches it he finds it red (it just became red), and he will wait since he doesn't have any skip available.

== include(page="template/taskfooter" task_id="police") ==
 

== include(page="template/taskfooter" task_id="police") ==