#P2832. 宅男小C

    ID: 1938 传统题 1000ms 512MiB 尝试: 273 已通过: 62 难度: 8 上传者: 标签>CF2400提高+/省选-二分答案二分查找凸性/单峰性判定交换论证前后缀最值一维前缀和

宅男小C

题目描述

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

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

输入格式

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

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

以下 NN 行,每行两个整数,分别表示 PiP_i 和 SiS_i。

输出格式

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

32 5 2
5 0
10 2
10 10 1
10 10
10 1 1
1 5
3
0
8

数据规模与约定

对于 40%40\% 的数据,M,Si≤2×106M,S_i\le 2 \times 10^6; 对于 100%100\% 的数据,M,Si≤1018M, S_i\le 10^{18},1≤T≤501 \le T \le 50,1≤F≤M1 \le F \le M,1≤N≤2001 \le N \le 200,1≤Pi≤M1 \le P_i \le M。