The Humanoid
Description
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:
- to absorb an astronaut with power strictly less humanoid power;
- to use green serum, if there is still one left;
- 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.
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$.
For each test case, in a separate line, print the maximum number of astronauts that a humanoid can absorb.
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.
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
Note
In the first case, you can proceed as follows:
- use green serum. $h = 1 \cdot 2 = 2$
- absorb the cosmonaut $2$. $h = 2 + \lfloor \frac{1}{2} \rfloor = 2$
- use green serum. $h = 2 \cdot 2 = 4$
- absorb the spaceman $1$. $h = 4 + \lfloor \frac{2}{2} \rfloor = 5$
- use blue serum. $h = 5 \cdot 3 = 15$
- absorb the spaceman $3$. $h = 15 + \lfloor \frac{8}{2} \rfloor = 19$
- absorb the cosmonaut $4$. $h = 19 + \lfloor \frac{9}{2} \rfloor = 23$