P3027 [USACO10OCT] Making Money G

FJ 又经营起了古董生意，买卖一些像奶牛圣诞树上的装饰之类的小玩意。他知道他会将他能存储的 $N(1 \le N \le 100)$ 件不同的奶牛古董每件都卖出。 而且如果他的钱足够多他可以买他想要的任意数量的古董（即他可以购买的古董数量没有限制）。他只有 $M(1\le M\le 10^5)$ 元钱来买古董，但他想要在他经商的第一年年末最大化他的利润（这有点难以解释）。 第 $i$ 种古董采购需要花费 $C_i(1\le C_i \le 10^5)$ 元钱，每卖掉一件可以获得 $R_i(1\le R_i \le 10^5)$ 元钱（每卖一件的利润为 $R_i-C_i$）。FJ 可以以任意顺序卖出他的货物。他并不需要花光他所有的钱来购买古董。 FJ 在他经商的第一年年末能得到的最大总利润（利润 = 初始钱数 - 总花费 + 总收入）是多少呢？输入数据保证这个数字不会超过 $10^9$。 假设 FJ 只有 $3$ 种古董而且开始时有 $M=17$ 元钱。下面是三种古董的花费和收入。 | 古董 | 花费 | 收入 | |:---:|:---:|:---:| | 1 | 2 | 4 | | 2 | 5 | 6 | | 3 | 3 | 7 | 在这种情况下，FJ 应该花 $15$ 元购买 $5$ 个 $3$ 号古董，再花 $2$ 元购买 $1$ 个 $1$ 号古董，总共 $17$ 元。他的利润是 $5\times(7-3)+1\times(4-2)=5\times4+1\times2=22$ 元。他不能获得比这更多的利润了。 提示：第二个样例很有挑战性，但我们的答案是正确的。

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

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

（由 ChatGPT 4o 翻译）