Problem D
Bus Ticket
Dang it! Your period ticket for the local Bus-Go-On-system (BGO) has expired. At first you wanted to buy a new period already today, but you suddenly realize that your next ticket would then expire a few days before your vacation starts, leaving a few trips you need to pay for individually anyways. Perhaps it is cheaper to pay for an individual trip now, allowing the next period ticket to cover more trips of the future?
Input
The first line of input contains four positive integers $s$, $p$, $m$, and $n$. $s$ ($1 \leq s \leq 10^9$) is the price of a single trip with the BGO, $p$ ($1 \leq p \leq 10^9$) is the price of a period ticket, $m$ ($1 \leq m \leq 10^9$) is the number of days the period ticket will cover, and $n$ ($1 \leq n \leq 10^6$) is the number of trips you plan to make in the future (until you die, and hence won’t need to pay for any further trips).
On the second line follows $n$ non-negative integers in non-decreasing order, $t_1, t_2, \ldots , t_ n$, where $t_ i$ ($0 \leq t_ i \leq 10^9$) is the number of days until you will make your $i$-th trip with the BGO.
Output
The smallest possible cost of making the trips.
| Sample Input 1 | Sample Output 1 |
|---|---|
10 25 30 6 0 1 2 30 30 32 |
45 |
