E. Гуманоид
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На некоторой космической станции работают $$$n$$$ космонавтов. Космонавт с номером $$$i$$$ ($$$1 \le i \le n$$$) имеет стойкость $$$a_i$$$.

На эту космическую станцию пробрался злобный гуманоид. Сила этого гуманоида равна $$$h$$$. Также гуманоид взял с собой две зелёных сыворотки и одну синюю сыворотку.

За одну секунду гуманоид может сделать любое из трёх действий:

  1. поглотить космонавта со стойкостью строго меньше силы гуманоида;
  2. употребить зелёную сыворотку, если такая ещё осталась;
  3. употребить синюю сыворотку, если такая ещё осталась.

При поглощении космонавта со стойкостью $$$a_i$$$, этот космонавт исчезает, а сила гуманоида увеличивается на $$$\lfloor \frac{a_i}{2} \rfloor$$$, то есть целую часть от $$$\frac{a_i}{2}$$$. Например, если гуманоид поглощает космонавта со стойкостью $$$4$$$, его сила увеличивается на $$$2$$$, а если гуманоид поглощает космонавта со стойкостью $$$7$$$, его сила увеличивается на $$$3$$$.

При употреблении зелёной сыворотки, эта сыворотка исчезает, а сила гуманоида увеличивается в $$$2$$$ раза.

При употреблении синей сыворотки, эта сыворотка исчезает, а сила гуманоида увеличивается в $$$3$$$ раза.

Гуманоиду интересно, какое максимальное количество космонавтов он сможет поглотить, если будет действовать оптимально.

Входные данные

В первой строке входных данных дано целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

В первой строке каждого набора входных данных даны целые числа $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество космонавтов и $$$h$$$ ($$$1 \le h \le 10^6$$$) — изначальная сила гуманоида.

Во второй строке каждого набора входных данных даны $$$n$$$ целых чисел $$$a_i$$$ ($$$1 \le a_i \le 10^8$$$) — стойкости космонавтов.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 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
Примечание

В первом случае можно действовать так:

  1. употребить зелёную сыворотку. $$$h = 1 \cdot 2 = 2$$$
  2. поглотить космонавта $$$2$$$. $$$h = 2 + \lfloor \frac{1}{2} \rfloor = 2$$$
  3. употребить зелёную сыворотку. $$$h = 2 \cdot 2 = 4$$$
  4. поглотить космонавта $$$1$$$. $$$h = 4 + \lfloor \frac{2}{2} \rfloor = 5$$$
  5. употребить синюю сыворотку. $$$h = 5 \cdot 3 = 15$$$
  6. поглотить космонавта $$$3$$$. $$$h = 15 + \lfloor \frac{8}{2} \rfloor = 19$$$
  7. поглотить космонавта $$$4$$$. $$$h = 19 + \lfloor \frac{9}{2} \rfloor = 23$$$