 2020 NA Regionals Practice Contest 5

Start

2021-01-16 09:00 AKST

2020 NA Regionals Practice Contest 5

End

2021-01-16 14:00 AKST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -375 days 3:08:26

5:00:00

0:00:00

Problem BBus 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