Mariuca received a piggy bank for her birthday. Ever since then, whenever she has spare change she puts in her piggy bank.
Today she saw the most beautiful Barbie doll. But unfortunately, Mariuca doesn't know if the money in her piggy bank is enough to buy it. In order to count her money she would have to break the piggy bank, but… if she doesn't have enough money she's left with no Barbie and no piggy bank.
Mariuca knows how much the piggy bank weighed when it was empty; she also knows how much each type of coin in the piggy bank weighs and, of course, she knows how much the full piggy bank weighs.

Task

Write a program that helps Mariuca find out what is the minimum amount that could be in her piggy bank.

Input Data

Input file barbie.in contains on the first line two positive integers separated by a space, GP PP (GP represents the weight of the empty piggy bank and PP the weight of the full piggy bank). The second line contains a positive integer N, representing the number of types of coins that could be in the piggy bank. The next N lines describe the N types of coins. Each of the N lines contain two positive integers, V G (V represents the coin's value and G represents its weight).

Output Data

Output file barbie.out will contain a single line with the minimum amount that could be in the piggy bank.

Constraints and Statements

1 <= GP <= PP <= 10000
1 <= N <= 500
1 <= V <= 50000, 1 <= G <=10000
All weights are expressed in grams.
Coin weights, and respectively values, do not necessarily have to be unique.
There is a solution for all test data.

Time limit: 0.1 seconds/test

prof. Emanuela Cerchez
"Grigore Moisil" Iasi Computer Science High School
Contact:emanuela.cerchez@gmail.com