Since JYY became obsessed with puzzles, he has become a complete shut-in. To solve the problem of food and clothing, JYY has to rely on ordering takeout to make a living.

Problem Statement

There are $N$ types of food in the takeout shop, numbered from 1 to $N$. The $i$-th type of food has a fixed price $P_i$ and a shelf life $S_i$. The $i$-th food will expire after $S_i$ days. JYY will not eat expired food.

For example, if JYY orders a food with a shelf life of 1 day today, he must eat it today or tomorrow; otherwise, the food can no longer be eaten. The shelf life can be 0 days, which means the food must be eaten on the day it is purchased.

JYY currently has $M$ dollars, and every time he orders takeout, he needs to pay an additional delivery fee of $F$ dollars to the delivery person. The delivery person is strong and can instantly bring any number of food items to JYY. JYY wants to know, under the condition that he can eat at least one non-expired meal every day, what is the maximum number of days he can stay at home?

Input

The first line contains three integers $M$, $F$, and $N$.

The next $N$ lines each contain two integers $P_i$ and $S_i$.

Output

Output a single integer representing the maximum number of days JYY can stay at home.

Examples

Input 1

32 5 2
5 0
10 2

Output 1

3

Note

JYY's optimal strategy is: Day 1: Buy one unit of food 1 and one unit of food 2, and eat one unit of food 1; Day 2: Eat one unit of food 2; Day 3: Buy one unit of food 1 and eat it.

Constraints

• For 10% of the data, $N = 1$;
• For 30% of the data, $M, S_i \le 300$;
• For 60% of the data, $M, S_i \le 300000$;
• For 100% of the data, $0 \le S_i \le 10^{18}$, $1 \le F, P_i, M \le 10^{18}$, $1 \le N \le 200$.