Minimizing Total Cost for Carpooling

We have a team of (N) OIers who must all reach the contest venue by time (S) (in minutes). To travel from the school gate to the destination, a taxi ride costs a flat fee of (D) dollars per ride, regardless of how many people are on board. However, each person also incurs a waiting cost equal to the number of minutes they wait at the gate (1 dollar per minute per person).

There are (K) taxis arriving at the school gate in order before time (S). The (i)-th taxi arrives at time (T_i) (in minutes, with (0 \le T_i \ S)) and has (Z_i) available seats. When a taxi arrives, you may choose to load any number of waiting OIers (up to the taxi’s capacity). You do not have to fill a taxi completely (you may choose 0 for that taxi, meaning you skip it). Note that if a taxi arrives at or after time (S) it is no longer available.

Every taxi ride (whenever used) costs (D) dollars (the fare is paid once per ride) and every person riding that taxi also pays a waiting cost equal to the taxi’s arrival time (since they wait from time 0 until the taxi arrives). Thus, if (x) people board a taxi arriving at time (T), the cost for that ride is (D + T \times x).

Determine the minimum total amount of money required so that all (N) OIers reach the contest venue on time. It is guaranteed that the total available capacity (possibly by using an extra taxi ride at time 0 if needed) is enough to cover (N) people.

Note: You may assume that besides the given (K) taxis, you can also call an immediate taxi at time (0) if needed. However, each taxi (whether called immediately at time 0 or one of the scheduled ones) can only be used once and can carry at most its available capacity. For an immediate taxi call at time 0, the waiting time is (0).

inputFormat

The first line contains four integers: \(N\), \(D\), \(S\), and \(K\) — the number of OIers, the taxi fare per ride, the deadline in minutes, and the number of scheduled taxis, respectively.

Then follow \(K\) lines. The \(i\)-th of these lines contains two integers \(T_i\) and \(Z_i\), representing the arrival time (in minutes) of the \(i\)-th taxi and its available seat count. The taxis are given in the order they arrive.

If the sum of the capacities of the \(K\) taxis is less than \(N\), you may call an immediate taxi at time 0. An immediate taxi has a waiting time of 0 minutes and costs \(D\) dollars, but can only be called once.

outputFormat

Output a single integer, the minimum total cost required to transport all \(N\) OIers to the contest venue on time.

sample

5 10 30 2
0 3
10 5

40