Challenge 24 Electronic Contest Practice

To visit a friend you haven't seen for a long time, you have to travel from city Alham to city Baynor by car. Luckily the shortest way is the Highway No 8, which is N km long (from Alham to Baynor). Your car's tank has a maximal capacity C, which is full at the beginning of the trip, and your car’s consumption is 1 liter/km.

However, it is not enough to make the whole trip without refueling, so you plan to stop at some gas stations along the road. Each gas station has a different price of fuel, due to the fact that they may belong to different companies. As a smart, but poor computer scientist, you would like to pay as little for the fuel as possible. Obviously, leaving the car with an empty tank on the road and walking is not your style (computer scientists are infamous for being lazy as well).

How would you do this, if you can assume that your GPS navigation software contains all the information about the gas stations on the highway?

Input

The first line contains N, the length of the trip. The second line contains C the fuel capacity of the car. The third line contains the number of gas stations. Then there is one line for each gas station containing the distance of the station from Alham and the price of the fuel there separated by a space character (both are integers).

Output

The output contains a single integer, the minimal total cost.

This is the text variant of the problem. Read more here about submitting solutions!

Example

Input
100
50
4
20 100
30 10
50 60
70 70
Output
1500