你永远买不到足够的幸福,所以我们再来一次!在这个版本中,你每个月只能购买$$$h_i = 1$$$单位的幸福,但月数大幅增加。我们正处于量子幸福和时间膨胀的领域。
作为一名物理学家,查理喜欢用简单而精确的方式规划自己的生活。
在接下来的 $$$m$$$ 个月里,从没有钱开始,查理将努力工作,每月赚取 $$$x$$$ 英镑。对于第 $$$i$$$ 个月 $$$(1 \le i \le m)$$$,将有一次支付成本 $$$c_i$$$ 英镑以获得一单位幸福的机会。您每月不能购买超过一件。
不允许借用。第 $$$i$$$ 个月赚到的钱只能在随后的第 $$$j$$$ 个月中花费 ($$$j>i$$$)。
由于物理学家不编码,请帮助查理找到可达到的最大幸福单位。
输入
输入的第一行包含 $$$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$$$。
输出
对于每个测试用例,输出一个整数——查理可以获得的最大幸福感。
示例
输入 #1
6 3 3 2 2 2 6 5 2 2 8 2 6 8 6 4 4 10 3 8 6 10 2 1 1 1 4 1 4 1 3 1 4 2 1 3 4 3
输出 #1
2 4 3 1 2 1