P2983 [USACO10FEB] Chocolate Buying S

题目描述

Bessie 和牛群都非常喜欢巧克力，所以农夫约翰打算为它们购买一些。

牛巧克力商店提供 $N$ 种巧克力（$1 \le N \le 100,000$），每种巧克力的数量基本上是无限的。每种巧克力 $i$ 的单价为 $P_i$（$1 \le P_i \le 10^{18}$），并且有 $C_i$（$1 \le C_i \le 10^{18}$）头牛想要这种巧克力。

农夫约翰有一个预算 $B$（$1 \le B \le 10^{18}$），他可以用来为牛群购买巧克力。他最多能满足多少头牛？所有的牛只想要一种巧克力，并且只会对这种巧克力感到满意。

考虑一个例子，假设农夫约翰有 $50$ 元可以花在 $5$ 种不同的巧克力上。总共有 11 头牛对各种巧克力有不同的偏好：

显然，农夫约翰不能购买第 5 种巧克力，因为他没有足够的钱。即使它只花费 $50$，这也是一个不划算的购买，因为只有一头牛会感到满意。

从价格较低的巧克力开始，他可以购买 1 块第 2 种巧克力，花费 $1 \times 1$，剩下 $50-1=49$；然后购买 3 块第 1 种巧克力，花费 $3 \times 5$，剩下 $49-15=34$；然后购买 2 块第 4 种巧克力，花费 $2 \times 7$，剩下 $34-14=20$；最后购买 2 块第 3 种巧克力，花费 $2 \times 10$，剩下 $20-20=0$。

这样，他就能满足 $1 + 3 + 2 + 2 = 8$ 头牛。

输入格式

第 1 行：两个用空格分隔的整数：$N$ 和 $B$。

第 $2\ldots N+1$ 行：第 $i$ 行包含两个用空格分隔的整数，定义巧克力类型 $i$：$P_i$ 和 $C_i$。

输出格式

第 1 行：一个整数，表示农夫约翰最多能满足的牛的数量。

输入输出样例 #1

输入 #1

5 50 
5 3 
1 1 
10 4 
7 2 
60 1 

输出 #1

8 

说明/提示

（由 ChatGPT 4o 翻译）