题目描述

FJ 进入了古玩生意，买卖像牛形圣诞树装饰品这样的古玩。

他知道他可以卖掉他能从一个包含 $N$ 种不同牛形古玩（$1 \leq N \leq 100$）的目录中进货的每一件古玩，并且他可以根据自己的心愿购买任意数量的每种古玩。

他只有 $M$ 的资金（$1 \leq M \leq 100,000$）可以投资，但希望在第一年末最大化他的利润（利润的定义稍有不同）。 古玩类型 $i$ 的购买成本为 $C_i$（$1 \leq C_i \leq 100,000$），每售出一个古玩可获得 $R_i$（$1 \leq R_i \leq 100,000$）的收入（利润为 $R_i - C_i$）。FJ 可以以任何方式混合搭配他出售的古玩。他在购买古玩时不需要花光所有的钱。

在第一年末，FJ 能获得的最大总利润是多少（利润 = 初始资金 - 所有成本 + 所有销售额）？这个数字保证小于 1,000,000,000。

考虑当 FJ 只有 3 种古玩并且开始时有 $M=17$ 的情况。以下是每种古玩的成本和收入：

在这种情况下，FJ 应该购买 5 个类型 3 的古玩，花费 15 钱，并再购买 1 个类型 1 的古玩，花费 2 钱，总共花费 17 钱。他的利润将是 $5 \times (7-3) + 1 \times (4-2) = 5 \times 4 + 1 \times 2 = 22$ 钱。根据成本和收入结构，他不能做得更好。

注意：第二个测试用例具有挑战性，但我们的答案是正确的。

输入格式

• 第 1 行：两个用空格分隔的整数：$N$ 和 $M$
• 第 2 行到第 $N+1$ 行：第 $i+1$ 行包含两个用空格分隔的整数：$C_i$ 和 $R_i$

输出格式

• 第 1 行：FJ 在给定成本和收入的情况下可以产生的最大利润

输入输出样例 #1

输入 #1

3 17 
2 4 
5 6 
3 7

输出 #1

22

说明/提示

（由 ChatGPT 4o 翻译）