#2832. 宅男小C

题目描述

众所周知，小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,Si <= 2*10^6；

对于100%的数据，M, Si<= 10^18，1 ≤ T ≤ 50，1 ≤ F ≤ M，1 ≤ N ≤ 200，1 ≤ Pi ≤ M。