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 头牛对各种巧克力有不同的偏好： | 巧克力类型 | 每块巧克力的价格 | 喜欢这种类型的牛数量 | |:-----------:|:-----------:|:-----------:| | $1$ | $5$ | $3$ | | $2$ | $1$ | $1$ | | $3$ | $10$ | $4$ | | $4$ | $7$ | $2$ | | $5$ | $60$ | $1$ | 显然，农夫约翰不能购买第 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 行：一个整数，表示农夫约翰最多能满足的牛的数量。

（由 ChatGPT 4o 翻译）