CF1974G Money Buys Less Happiness Now

你永远买不够幸福，所以我们又来了！在这个版本中，你每个月只能买 $h_i = 1$ 单位的幸福，但月份数大大增加了。我们进入了量子幸福和时间膨胀的领域。 作为一名物理学家，Charlie 喜欢以简单而精确的方式规划生活。 在接下来的 $m$ 个月里，Charlie 从零开始，每个月努力工作赚取 $x$ 英镑。在第 $i$ 个月（$1 \le i \le m$），他有一次机会花费 $c_i$ 英镑购买一个单位的幸福。你每个月最多只能买一个单位。 不允许借钱。在第 $i$ 个月赚到的钱只能在之后的第 $j$ 个月（$j>i$）花掉。 由于物理学家不会编程，请你帮 Charlie 求出他最多能获得多少单位的幸福。

第一行输入一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。 每个测试用例的第一行包含两个整数 $m$ 和 $x$（$1 \le m \le 2 \cdot 10^5$，$1 \le x \le 10^3$），分别表示总月份数和每月工资。 每个测试用例的第二行包含 $m$ 个整数 $c_1, c_2, \dots, c_m$（$1 \leq c_i \leq 10^3$），表示每个月购买一个单位幸福的花费。 保证所有测试用例中 $m$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一个整数，表示 Charlie 最多能获得的幸福单位数。

由 ChatGPT 4.1 翻译