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

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