Problem C
Tycho

The planetary exploration vehicle Tycho VIII needs to get back to the home base after collecting mineral samples. Tycho travels in a straight line from position $0$ to the home base at position $b$. While moving, it advances at a slow but steady pace of $1$ unit per second. Every second, Tycho takes $1$ unit of environmental damage from the harsh planetary conditions.

The situation is made even worse by radiation from a nearby pulsar, which adds $d$ additional units of damage every $p$ seconds. However, the radiation damage can be avoided by seeking shelter in one of $n$ different hiding spots—caves, vegetation, large rocks, carcasses of the planet’s megafauna—along the way. Tycho can choose to stand still at any point for any integer number of seconds.

The starting position $0$ and the home base at $b$ are both sheltered, so Tycho takes no radiation damage there.

What is the minimum damage Tycho will take on its journey back to the home base?

Example

Consider the situation where the home base is at position $18$ and there are shelters at positions $8$ and $15$.

Assume that the pulsar’s period is $4$, so unsheltered Tycho would take damage at times $4$, $8$, $12$, etc. If Tycho leaves from the starting position (where it’s sheltered) at time $0$, it can reach the first shelter after $8$ seconds, incurring radiation damage $d$ at time $4$ (but none at time $8$ because it’s sheltered then). Continuing without stopping, it reaches the home base at time $18$, incurring $d+d$ more units of radiation damage (at times $12$ and $16$, respectively). This way it incurs $d+d+d=3d$ units of radiation damage and $18$ units of environmental damage. If instead Tycho waits at the $2$nd shelter (at position $15$) for $1$ second, the pulse at time $16$ causes it no damage, and it reaches the home base at time $19$ with a total of $2d + 19$ units of damage. This is better for most values of $d$. The two situations are shown here:

If the pulsar’s period is $10$, Tycho can wait at the starting position for $2$ seconds and then just go home without stopping at any shelter. Thus it passes the $1$st shelter (at position $8$) at just the right moment when the pulsar flares and arrives at the home base at time $20$, for a total of $20$ environmental damage and no radiation damage at all.

Input

The first line consists of four integers $b$, $p$, $d$, and $n$, separated by single spaces: the location $b$ of the home base, the pulsar’s flare period $p$, the additional radiation damage $d$ caused by each flare of the pulsar, the number $n$ of the shelters. The following $n$ lines each contain an integer giving the shelter locations $a_1$, $\ldots $, $a_ n$, with $0<a_1<\cdots <a_ n< b$.

Output

Print a single integer: the minimum amount of damage Tycho must take to reach $b$.

Constraints and Scoring

You can assume $p < b$ and $n < b$. We always have $1\leq b\leq 10^{12}$, $0\leq d \leq 10^6$, and $0\leq n \leq 10^5$.

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group. Your final score will be the maximum score of a single submission.

$^*$ In test group $1$, Tycho may still need to wait at position $0$ before it starts moving. For example, sample inputs $2$, $3$, and $4$ belong to test group $1$.

18 4 5 2
8
15

29

18 4 0 2
8
15

18

18 10 100 2
8
15

20

18 4 100 0

418

65 20 100 3
14
25
33

172