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

Poveste şi cerinţă...

Fearsome William is still free, and the Police is searching him in Murder Boulevard!
 
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$.
 
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.
 
William wants to reach his nest as quickly as possible, but he doesn't want to attract too much attention.
 
Therefore, he travels at a constant speed of $1$ meter per second (the speed limit), and he will stop and wait if he's at a red semaphore.
 
Since he's very impatient, sometimes he may cross the red semaphore without waiting for the green, but he can do so at most $R$ times.
 
Which is the least amount of time William needs to reach his nest?

h2. Date de intrare

Fişierul de intrare $police.in$ ...

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$.
 

h2. Date de ieşire

În fişierul de ieşire $police.out$ ...

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$
* $1 ≤ T ≤ 1000$
* $N < L &le; 10^9$
* $X[i] < L$, for each semaphore
* $X[i] < X[i+1]$ for each $i$ from $0$ to $n-2$

h2. Exemplu
table(example). |_. police.in |_. police.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 3 1 3 10
1 5 9
| 11
|
 
table(example). |_. police.in |_. police.out |
| 1 0 5 10
5
| 15

|
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.
 
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}
 
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.
 
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") ==