17981번 - Bus Ticket 다국어

Dang it! Your period ticket for the local Bus-Go-Onsystem (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?

The first line of input contains four positive integers s, p, m, and n. s (1 ≤ s ≤ 10⁹) is the price of a single trip with the BGO, p (1 ≤ p ≤ 10⁹) is the price of a period ticket, m (1 ≤ m ≤ 10⁹) is the number of days the period ticket will cover, and n (1 ≤ p ≤ 10⁶) 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₁, t₂, . . . , t_n, where t_i (0 ≤ t_i ≤ 10⁹) is the number of days until you will make your i-th trip with the BGO.

The smallest possible cost of making the trips.