Description

There are $n$ types of food, 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 type expires 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, then JYY must eat it today or tomorrow; otherwise, this food can no longer be eaten. The shelf life can be $0$ days, in which case the food must be eaten on the day of purchase.

JYY currently has $m$ yuan. Each time he places a takeout order, he must additionally pay a delivery fee of $f$ yuan.

The delivery person is strong and can instantly bring JYY arbitrarily many portions of food in one order. JYY wants to know, while ensuring that he can eat at least one unexpired takeout meal every day, for how many days at most can he stay at home.

Input Format

The first line contains three integers, representing $m, f, n$.

Lines $2$ to $(n + 1)$ each contain two integers; in line $(i + 1)$, the integers denote the price $p_i$ and the shelf life $s_i$ of the $i$-th type of food.

Output Format

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

32 5 2
5 0
10 2

3

Hint

Explanation of Sample Input/Output 1

JYY’s best strategy is:

• On day 1, buy one portion of food $1$ and one portion of food $2$, and eat one portion of food $1$.
• On day 2, eat one portion of food $2$.
• On day 3, buy one portion of food $1$ and eat it.

Constraints

For all test points, it is guaranteed that $1 \leq n \leq 200$, $0 \leq s_i \leq 10^{18}$, $1 \leq f, p_i, m \leq 10^{18}$.

Translated by ChatGPT 5