P3027 [USACO10OCT] Making Money G

FJ又经营起了古董生意，买卖一些像奶牛圣诞树上的装饰之类的小玩意。他知道他会将他能存储的N(1

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$ 的情况。以下是每种古玩的成本和收入： | 古玩 | 成本 $C_i$ | 收入 $R_i$ | |------|-----------|-----------| | 1 | 2 | 4 | | 2 | 5 | 6 | | 3 | 3 | 7 | 在这种情况下，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 在给定成本和收入的情况下可以产生的最大利润

（由 ChatGPT 4o 翻译）