CF1974E Money Buys Happiness

作为一名物理学家，Charlie 喜欢以简单而精确的方式规划自己的生活。 在接下来的 $m$ 个月里，Charlie 从零开始，每月努力工作并赚取 $x$ 英镑。在第 $i$ 个月（$1 \le i \le m$），他有一次机会花费 $c_i$ 英镑来获得 $h_i$ 的幸福值。 不允许借钱。在第 $i$ 个月赚到的钱只能在之后的第 $j$ 个月（$j>i$）花费。 由于物理学家不会编程，请你帮 Charlie 求出他能获得的最大幸福值总和。

输入的第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试用例的数量。 每个测试用例的第一行包含两个整数 $m$ 和 $x$（$1 \le m \le 50$，$1 \le x \le 10^8$），分别表示总月数和每月工资。 接下来的 $m$ 行中，第 $i$ 行包含两个整数 $c_i$ 和 $h_i$（$0 \le c_i \le 10^8$，$1 \le h_i \le 10^3$），分别表示第 $i$ 个月的花费和可获得的幸福值。注意，有些幸福值可能是免费的（即某些 $c_i=0$）。 保证所有测试用例中 $\sum_i h_i$ 的总和不超过 $10^5$。

对于每个测试用例，输出一个整数，表示 Charlie 能获得的最大幸福值总和。

在第一个测试用例中，Charlie 只在月末拿到工资，因此无法购买任何东西。 在第二个测试用例中，Charlie 在第一个月获得了免费的幸福值。 在第三个测试用例中，最优策略是在第二个月购买幸福值。即使最后还有剩余的钱，Charlie 也无法回到过去获得第一个月的幸福值。 由 ChatGPT 4.1 翻译