31976번 - 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 minumum damage Tycho will take on its journey back to the home base?

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 2ドルd + 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.

입력

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

출력

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

제한

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

서브태스크

힌트