← 返回题目列表

Codeforces · 1974/G

G. 金钱现在买不到幸福

中文机器翻译题面 查看原题

你永远买不到足够的幸福,所以我们再来一次!在这个版本中,你每个月只能购买$$$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