宅男小C

时间限制:10s      空间限制:256MB

题目描述

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

 

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


输入格式

每个测试点包含多组测试数据;
每个测试数据第一行三个整数M,F,N,如题目描述中所述;
以下N行,每行两个整数,分别表示PiSi


输出格式

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


样例输入

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。


题目来源

没有写明来源