311279: CF1959G. The Humanoid

G. The Humanoidtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

There are $n$ astronauts working on some space station. An astronaut with the number $i$ ($1 \le i \le n$) has power $a_i$.

An evil humanoid has made his way to this space station. The power of this humanoid is equal to $h$. Also, the humanoid took with him two green serums and one blue serum.

In one second , a humanoid can do any of three actions:

1. to absorb an astronaut with power strictly less humanoid power;
2. to use green serum, if there is still one left;
3. to use blue serum, if there is still one left.

When an astronaut with power $a_i$ is absorbed, this astronaut disappears, and power of the humanoid increases by $\lfloor \frac{a_i}{2} \rfloor$, that is, an integer part of $\frac{a_i}{2}$. For example, if a humanoid absorbs an astronaut with power $4$, its power increases by $2$, and if a humanoid absorbs an astronaut with power $7$, its power increases by $3$.

After using the green serum, this serum disappears, and the power of the humanoid doubles, so it increases by $2$ times.

After using the blue serum, this serum disappears, and the power of the humanoid triples, so it increases by $3$ times.

The humanoid is wondering what the maximum number of astronauts he will be able to absorb if he acts optimally.

Input

The first line of each test contains an integer $t$ ($1 \le t \le 10^4$) — number of test cases.

The first line of each test case contains integers $n$ ($1 \le n \le 2 \cdot 10^5$) — number of astronauts and $h$ ($1 \le h \le 10^6$) — the initial power of the humanoid.

The second line of each test case contains $n$ integers $a_i$ ($1 \le a_i \le 10^8$) — powers of astronauts.

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

Output

For each test case, in a separate line, print the maximum number of astronauts that a humanoid can absorb.

ExampleInput

8
4 1
2 1 8 9
3 3
6 2 60
4 5
5 1 100 5
3 2
38 6 3
1 1
12
4 6
12 12 36 100
4 1
2 1 1 15
3 5
15 1 13

Output

4
3
3
3
0
4
4
3

Note

In the first case, you can proceed as follows:

1. use green serum. $h = 1 \cdot 2 = 2$
2. absorb the cosmonaut $2$. $h = 2 + \lfloor \frac{1}{2} \rfloor = 2$
3. use green serum. $h = 2 \cdot 2 = 4$
4. absorb the spaceman $1$. $h = 4 + \lfloor \frac{2}{2} \rfloor = 5$
5. use blue serum. $h = 5 \cdot 3 = 15$
6. absorb the spaceman $3$. $h = 15 + \lfloor \frac{8}{2} \rfloor = 19$
7. absorb the cosmonaut $4$. $h = 19 + \lfloor \frac{9}{2} \rfloor = 23$

题目大意：
在某个空间站上有n个宇航员，第i个宇航员（1≤i≤n）的力量为a_i。一个邪恶的人形生物来到了这个空间站，其力量为h。人形生物带来了两个绿色血清和一个蓝色血清。每秒钟，人形生物可以进行以下三种行动之一：

1. 吸收一个力量严格小于人形生物力量的宇航员；
2. 如果还有剩余，使用一个绿色血清；
3. 如果还有剩余，使用一个蓝色血清。

当一个力量为a_i的宇航员被吸收后，该宇航员消失，人形生物的力量增加⌊a_i/2⌋，即a_i/2的整数部分。使用绿色血清后，该血清消失，人形生物的力量加倍，即增加2倍。使用蓝色血清后，该血清消失，人形生物的力量增加至三倍，即增加3倍。

问人形生物如果行动最优，最多能吸收多少个宇航员。

输入输出数据格式：
输入：
- 第一行包含一个整数t（1≤t≤10^4），表示测试用例的数量。
- 每个测试用例的第一行包含两个整数n（1≤n≤2×10^5）和h（1≤h≤10^6），分别表示宇航员数量和人形生物的初始力量。
- 每个测试用例的第二行包含n个整数a_i（1≤a_i≤10^8），表示宇航员的力量。
- 保证所有测试用例的n之和不超过2×10^5。

输出：
- 对于每个测试用例，输出一行，表示人形生物最多能吸收的宇航员数量。

示例输入输出：
输入：
```
8
4 1
2 1 8 9
3 3
6 2 60
4 5
5 1 100 5
3 2
38 6 3
1 1
12
4 6
12 12 36 100
4 1
2 1 1 15
3 5
15 1 13
```
输出：
```
4
3
3
3
0
4
4
3
```题目大意： 在某个空间站上有n个宇航员，第i个宇航员（1≤i≤n）的力量为a_i。一个邪恶的人形生物来到了这个空间站，其力量为h。人形生物带来了两个绿色血清和一个蓝色血清。每秒钟，人形生物可以进行以下三种行动之一： 1. 吸收一个力量严格小于人形生物力量的宇航员； 2. 如果还有剩余，使用一个绿色血清； 3. 如果还有剩余，使用一个蓝色血清。 当一个力量为a_i的宇航员被吸收后，该宇航员消失，人形生物的力量增加⌊a_i/2⌋，即a_i/2的整数部分。使用绿色血清后，该血清消失，人形生物的力量加倍，即增加2倍。使用蓝色血清后，该血清消失，人形生物的力量增加至三倍，即增加3倍。 问人形生物如果行动最优，最多能吸收多少个宇航员。 输入输出数据格式： 输入： - 第一行包含一个整数t（1≤t≤10^4），表示测试用例的数量。 - 每个测试用例的第一行包含两个整数n（1≤n≤2×10^5）和h（1≤h≤10^6），分别表示宇航员数量和人形生物的初始力量。 - 每个测试用例的第二行包含n个整数a_i（1≤a_i≤10^8），表示宇航员的力量。 - 保证所有测试用例的n之和不超过2×10^5。 输出： - 对于每个测试用例，输出一行，表示人形生物最多能吸收的宇航员数量。 示例输入输出： 输入： ``` 8 4 1 2 1 8 9 3 3 6 2 60 4 5 5 1 100 5 3 2 38 6 3 1 1 12 4 6 12 12 36 100 4 1 2 1 1 15 3 5 15 1 13 ``` 输出： ``` 4 3 3 3 0 4 4 3 ```