On a national highway, there are K toll stations, numbered from 1 to K. A vehicle passes through these stations multiple times during its journey.

Each time the vehicle passes through a station, the following toll policy applies:

• The standard toll fee for passing through any station is fee. If the vehicle pays the fee at station i at time t, it receives a priority ticket.
• This priority ticket allows the vehicle to pass once, free of charge, at any other station j such that j ≠ i. The ticket is valid for time_limit minutes from the time it was issued. Each ticket can be used at most once.
• If multiple valid tickets exist at the time of a passage, at most one may be used. If a valid ticket is available when passing through a station, the vehicle may choose to use it instead of paying the fee.

You are given the full list of the vehicle's passages, including the station number and the time of passage (in minutes). The passage times are strictly increasing. Your task is to compute the minimum total amount of money the vehicle owner must pay for the entire journey.

Input

The first line contains four positive integers K (the number of toll stations), fee, time_limit, and N (the total number of passages).

Each next N lines contains the information for a single passage, consisting of two positive integers: station[i] (1 ≤ stationi ≤ K) and time[i] representing the station number and the time of passage in minutes, relatively. (1 ≤ i ≤ N)

Note: The passage times are always strictly increasing. All values do not exceed 10⁹. There are 50% testcases of K ≤ 2

Output

An integer representing the total paid amount.

Example

Input

2 100 10 3
1 0
2 5
1 12

Output

200