311363: CF1974G. Money Buys Less Happiness Now

G. Money Buys Less Happiness Now time limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

You can never buy enough happiness, so here we go again! In this version, you can only buy $h_i = 1$ unit of happiness each month, but the number of months is hugely increased. We are in the realm of quantum happiness and time dilation.

Being a physicist, Charlie likes to plan his life in simple and precise terms.

For the next $m$ months, starting with no money, Charlie will work hard and earn $x$ pounds per month. For the $i$-th month $(1 \le i \le m)$, there'll be a single opportunity of paying cost $c_i$ pounds to obtain one unit of happiness. You cannot buy more than one unit each month.

Borrowing is not allowed. Money earned in the $i$-th month can only be spent in a later $j$-th month ($j>i$).

Since physicists don't code, help Charlie find the maximum reachable units of happiness.

Input

The first line of the input contains $t$ ($1 \leq t \leq 10^4$) — the number of test cases.

The first line of each test case contains two integers, $m$ and $x$ ($1 \le m \le 2 \cdot 10^5$, $1 \le x \le 10^3$) — the total number of months and the monthly salary.

The second line of each test case contains $m$ integers $c_1, c_2, \dots, c_m$ ($1 \leq c_i \leq 10^3$) — the cost of one unit of happiness for each month.

It is guaranteed that sum of $m$ over all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, output one integer — the maximal amount of happiness Charlie can get.

ExampleInput

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

Output

2
4
3
1
2
1

题目大意：
这个题目是关于如何最大化幸福感的。在这个问题中，Charlie每个月可以赚取一定的金额，并且每个月有一次机会以一定的代价购买1单位的幸福感。Charlie不能透支，即他在第i个月赚的钱只能用于之后的月份。目标是计算Charlie可以获得的最大幸福感单位数。

输入数据格式：
- 输入的第一行包含一个整数t，表示测试用例的数量。
- 每个测试用例有两行：
- 第一行包含两个整数m和x，分别表示总月份数和每月的薪水。
- 第二行包含m个整数c_1, c_2, ..., c_m，分别表示每个月购买1单位幸福感的代价。

输出数据格式：
- 对于每个测试用例，输出一个整数，表示Charlie可以获得的最大幸福感单位数。

例子：
```
输入
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

输出
2
4
3
1
2
1
```

LaTeX格式公式：
由于题目中并没有包含数学公式，所以这里不需要提供LaTeX格式的公式。题目大意： 这个题目是关于如何最大化幸福感的。在这个问题中，Charlie每个月可以赚取一定的金额，并且每个月有一次机会以一定的代价购买1单位的幸福感。Charlie不能透支，即他在第i个月赚的钱只能用于之后的月份。目标是计算Charlie可以获得的最大幸福感单位数。 输入数据格式： - 输入的第一行包含一个整数t，表示测试用例的数量。 - 每个测试用例有两行： - 第一行包含两个整数m和x，分别表示总月份数和每月的薪水。 - 第二行包含m个整数c_1, c_2, ..., c_m，分别表示每个月购买1单位幸福感的代价。 输出数据格式： - 对于每个测试用例，输出一个整数，表示Charlie可以获得的最大幸福感单位数。 例子： ``` 输入 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 输出 2 4 3 1 2 1 ``` LaTeX格式公式： 由于题目中并没有包含数学公式，所以这里不需要提供LaTeX格式的公式。