Description

题目背景

你永远买不到足够的幸福，所以我们又来了！在这个版本中，你每个月只能购买 $h_i = 1$ 个单位的幸福，但月数却大大增加了。我们进入了量子幸福和时间膨胀的境界。

题目描述

作为一名物理学家，$kkkw$喜欢用简单精确的语言来规划自己的生活。

在接下来的 $m$ 个月里，从没有钱开始，查理将努力工作，每月赚取 $x$ 英镑。在第 $i$ 个月的第 $(1 \le i \le m)$ 个月里，将有一次机会，付出 $c_i$ 英镑的代价，获得一个单位的幸福。每月不能购买超过一个单位。

不允许借贷。在 $i$ 月赚到的钱只能在之后的 $j$ 月（ $j>i$ ）使用。

既然物理学家不会写代码，那就帮$kkkw$找出可达到的最大幸福单位吧。

输入格式

输入的第一行包含 $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

输入 #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

说明/提示

$30 \%$的数据，$1 \le m \le 1000$

$50 \%$的数据，$1 \le m \le 10^5 ,1\le x,c_i \le 10$

$100 \%$的数据，$1 \le m \le 2 \times 10^5 ,1\le x \le 10^3$