题目描述

众所周知，小 C 是个宅男，所以他的每天的食物要靠外卖来解决。小 C 现在有 $M$ 元钱，他想知道这些钱他最多可以吃多少天。

餐厅提供 $N$ 种食物，每种食物有两个属性，单价 $P_i$ 和保质期 $S_i$，表示小 C 需要花 $P_i$ 元才能买到足够一天吃的这种食物，并且需要在送到 $S_i$ 天内吃完，否则食物会变质，就不能吃了，若 $S_i$ 为 0 则意味着必须在送到当天吃完。另外，每次送餐需要额外 $F$ 元送餐费。

输入格式

每个测试点包含多组测试数据；

每个测试数据第一行三个整数 $M,F,N$，如题目描述中所述；

以下 $N$ 行，每行两个整数，分别表示 $P_i$ 和 $S_i$。

输出格式

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

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 T \le 50$，$1 \le F \le M$，$1 \le N \le 200$，$1 \le P_i \le M$。