宅男小C

众所周知，小 C 是个宅男，每天的食物都需要通过外卖解决。小 C 现在有 $M$ 元，他想知道这些钱最多能让他吃多少天。

餐厅提供 $N$ 种食物。每种食物有两个属性：单价 $P_i$ 和保质期 $S_i$。小 C 花费 $P_i$ 元，可以购买足够吃一天的第 $i$ 种食物；这种食物必须在送到后的 $S_i$ 天内吃完，否则就会变质，无法食用。若 $S_i=0$，则表示食物必须在送到当天吃完。

此外，每次送餐还需要额外支付 $F$ 元送餐费。

输入格式

输入包含若干组测试数据，读至文件结束。

对于每组测试数据，第一行包含三个整数 $M$、$F$、$N$，含义如题目描述所述。

接下来 $N$ 行，每行包含两个整数 $P_i$、$S_i$，分别表示第 $i$ 种食物的单价和保质期。

输出格式

对于每组测试数据，输出一行一个整数，表示小 C 最多可以吃的天数。

样例输入

32 5 2
5 0
10 2
10 10 1
10 10
10 1 1
1 5

样例输出

3
0
8

数据范围

• 对于 $40\%$ 的数据，$M,S_i\le 2\times 10^6$；
• 对于 $100\%$ 的数据，$M,S_i\le 10^{18}$，$1\le F\le M$，$1\le N\le 200$，$1\le P_i\le M$；
• 设一个输入文件中包含的测试数据组数为 $T$，则 $1\le T\le 50$，输入中不单独给出 $T$。

来源与许可

本题题面与测试数据整理自 BZOJ。

样例 1

输入

32 5 2
5 0
10 2
10 10 1
10 10
10 1 1
1 5

输出

3
0
8