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.


-----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.


-----Examples-----

Input
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:

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$

Source: codeforces | Difficulty: MEDIUM
Tags: Dynamic programming

Sorting

Complete search


Solutions:
import sys, math, itertools
from collections import Counter, deque, defaultdict
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush, heapify
mod = 998244353
INF = float('inf')

def inp():
	return int(sys.stdin.readline())

def inpl():
	return list(map(int, sys.stdin.readline().split()))

def inpl_1():
	return list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))

def inplm():
	return map(int, sys.stdin.readline().split())

def inpl_1m():
	return map(lambda x: int(x) - 1, sys.stdin.readline().split())

def inps():
	tmp = sys.stdin.readline()
	return list(tmp[:len(tmp) - 1])

def inpsl(x):
	tmp = sys.stdin.readline()
	return list(tmp[:x])

def err(x):
	print(x)
	exit()
sys.setrecursionlimit(10 ** 8)
for _ in range(inp()):
	(n, h) = inplm()
	a = inpl()
	a.sort()

	def dfs(i, g, b, h):
		while i < n:
			ast = a[i]
			if h > ast:
				h += ast // 2
				i += 1
				continue
			else:
				break
		if i == n:
			return n
		mx = i
		if g:
			mx = max(mx, dfs(i, g - 1, b, h * 2))
		if b:
			mx = max(mx, dfs(i, g, b - 1, h * 3))
		return mx
	print(dfs(0, 2, 1, h))


import sys
from collections import *
sys.setrecursionlimit(10 ** 5)
itr = (line for line in sys.stdin.read().strip().split('\n'))
INP = lambda : next(itr)

def ni():
	return int(INP())

def nl():
	return [int(_) for _ in INP().split()]

def solve(n, p, arr):
	arr.sort()

	def rec(dob, tri, i, cur, cnt):
		while i < len(arr):
			if cur > arr[i]:
				cur += arr[i] // 2
				cnt += 1
				i += 1
			else:
				o = False
				o2 = False
				if dob < 2:
					one = rec(dob + 1, tri, i, cur * 2, cnt)
					o = True
				if tri < 1:
					o2 = True
					two = rec(dob, tri + 1, i, cur * 3, cnt)
				if o and o2:
					return max(one, two)
				if o:
					return one
				if o2:
					return two
				return cnt
		return cnt
	print(rec(0, 0, 0, p, 0))
t = ni()
for _ in range(t):
	(n, p) = nl()
	arr = nl()
	solve(n, p, arr)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()

	def F(a, b):
		res = m
		cnt = 0
		i = 0
		for x in a:
			while res <= x:
				if cnt < 3:
					res *= b[cnt]
				else:
					return i
				cnt += 1
			res += x // 2
			i += 1
		return i
	print(max(F(a, [2, 2, 3]), F(a, [2, 3, 2]), F(a, [3, 2, 2])))


def cal(he, a, t, th, n, arr):
	for i in range(a, n):
		if he > arr[i]:
			he += arr[i] // 2
		elif t == 0 and th == 0:
			return i
		elif t == 0:
			return cal(he * 3, i, 0, 0, n, arr)
		elif th == 0:
			return cal(he * 2, i, t - 1, 0, n, arr)
		else:
			return max(cal(he * 3, i, t, 0, n, arr), cal(he * 2, i, t - 1, th, n, arr))
	return n
for jj in range(int(input())):
	(m, h) = [int(i) for i in input().split()]
	al = [int(i) for i in input().split()]
	al.sort()
	print(cal(h, 0, 2, 1, m, al))


def solve():
	[n, h1] = [int(n) for n in input().split()]
	a = [int(n) for n in input().split()]
	numA = []
	a.sort()
	PO = [[2, 2, 3], [2, 3, 2], [3, 2, 2]]
	for p in PO:
		num = 0
		h = h1
		for i in a:
			while h <= i:
				if p:
					h *= p.pop()
					continue
				else:
					break
			if h <= i:
				continue
			h += i // 2
			num += 1
		numA.append(num)
	print(max(numA))
for _ in range(int(input())):
	solve()


def main():
	t = int(input())
	while t > 0:
		ret = 0
		(n, h) = map(int, input().split())
		pa = list(map(int, input().split()))
		pa.sort()

		def s_seq(ss):
			ph = h
			indx = 0
			while indx < n:
				if ph > pa[indx]:
					ph = ph + pa[indx] // 2
					indx += 1
				elif ss:
					ph = ph * ss.pop(0)
				else:
					break
			return indx
		print(max(s_seq([2, 2, 3]), s_seq([2, 3, 2]), s_seq([3, 2, 2])))
		t -= 1
main()


def calc():
	(n, h) = [int(el) for el in input().split()]
	arr = [int(el) for el in input().split()]
	arr.sort()
	ans = 0
	tmp = [[2, 2, 3, 1], [2, 3, 2, 1], [3, 2, 2, 1]]
	for j in range(3):
		xx = tmp[j]
		(cur, i) = (h, 0)
		for el in xx:
			while i < n and cur > arr[i]:
				cur += arr[i] // 2
				i += 1
			cur *= el
		ans = max(ans, i)
	print(ans)
for _ in range(int(input())):
	calc()


T = int(input())

def best(h, astro, serum_order):
	absorbed = 0
	serum_index = 0
	for p in astro:
		while p >= h:
			if serum_index == 3:
				return absorbed
			h *= serum_order[serum_index]
			serum_index += 1
		absorbed += 1
		h += p // 2
	return absorbed
for _ in range(T):
	(n, h) = map(int, input().split())
	astro = list(map(int, input().split()))
	astro.sort()
	print(max(best(h, astro, (3, 2, 2)), best(h, astro, (2, 3, 2)), best(h, astro, (2, 2, 3))))


def solve():
	(n, h) = map(int, input().split())
	asts = list(map(int, input().split()))
	asts.sort()
	return max(strat(h, asts, [2, 2, 3]), strat(h, asts, [2, 3, 2]), strat(h, asts, [3, 2, 2]))

def strat(h, asts, serums):
	i = 0
	out = 0
	n = len(asts)
	while i < n:
		a = asts[i]
		if a < h:
			h += a // 2
			out += 1
			i += 1
		elif serums:
			h *= serums.pop()
		else:
			break
	return out
for _ in range(int(input())):
	print(solve())


def solve(numDouble, numTriple, h, powers, k):
	(optimal, optimal2, optimal3) = (0, 0, 0)
	for i in range(k, len(powers)):
		p = powers[i]
		if h > p:
			h += p // 2
			optimal += 1
		elif numDouble <= 0 and numTriple <= 0:
			return optimal
		else:
			optimal2 = 0
			optimal3 = 0
			if numDouble > 0:
				optimal2 = solve(numDouble - 1, numTriple, h * 2, powers, i)
			if numTriple > 0:
				optimal3 = solve(numDouble, numTriple - 1, h * 3, powers, i)
			optimal += max(optimal2, optimal3)
			break
	return optimal
t = int(input())
for i in range(t):
	(n, h) = (int(i) for i in input().split(' '))
	powers = [int(i) for i in input().split(' ')]
	assert len(powers) == n
	powers = sorted(powers)
	print(solve(2, 1, h, powers, 0))


g1 = [2, 2, 3]
g2 = [2, 3, 2]
g3 = [3, 2, 2]

def find_1(ls, n, h):
	j = i = 0
	while j <= 3 and i < n:
		while i < n and ls[i] < h:
			h += ls[i] // 2
			i += 1
		if j < 3 and i < n:
			h *= g1[j]
			j += 1
		else:
			break
	return i

def find_2(ls, n, h):
	j = i = 0
	while j <= 3 and i < n:
		while i < n and ls[i] < h:
			h += ls[i] // 2
			i += 1
		if i == n:
			break
		if j < 3:
			h *= g2[j]
			j += 1
		else:
			break
	return i

def find_3(ls, n, h):
	j = i = 0
	while j <= 3 and i < n:
		while i < n and ls[i] < h:
			h += ls[i] // 2
			i += 1
		if i == n:
			break
		if j < 3:
			h *= g3[j]
			j += 1
		else:
			break
	return i
t = int(input())
for i in range(t):
	(n, h) = map(int, input().split())
	ls = list(map(int, input().split()))
	ls.sort()
	print(max(find_1(ls, n, h), find_2(ls, n, h), find_3(ls, n, h)))


import math

def mxeat(arr, n, h, ng, nb, ind):
	if ind >= n:
		return 0
	ans = 0
	while ind < n and arr[ind] < h:
		h += math.floor(arr[ind] / 2)
		ans += 1
		ind += 1
	a1 = 0
	a2 = 0
	if ind < n:
		if ng > 0:
			a1 = mxeat(arr, n, h * 2, ng - 1, nb, ind)
		if nb > 0:
			a2 = mxeat(arr, n, h * 3, ng, nb - 1, ind)
	ans += max(a1, a2)
	return ans
tem = int(input())
for i in range(tem):
	l1 = input().split()
	l2 = input().split()
	arr = []
	n = int(l1[0])
	h = int(l1[1])
	for i in range(n):
		arr.append(int(l2[i]))
	arr.sort()
	print(mxeat(arr, n, h, 2, 1, 0))


def func(f, s, t, n, h, a):
	ans = 0
	i = 0
	while i < n:
		if h > a[i]:
			ans += 1
			h += a[i] // 2
		elif f != 0:
			h = h * f
			f = 0
			i -= 1
		elif s != 0:
			h = h * s
			s = 0
			i -= 1
		elif t != 0:
			h = h * t
			t = 0
			i -= 1
		i += 1
	return ans
t = int(input())
for _ in range(t):
	(n, h) = map(int, input().split())
	a = [int(i) for i in input().split()]
	a.sort()
	print(max(func(3, 2, 2, n, h, a), func(2, 2, 3, n, h, a), func(2, 3, 2, n, h, a)))


from functools import lru_cache
import sys
sys.setrecursionlimit(10000)

def read_int():
	return [int(x) for x in input().split()]

def solve(n, h, a):
	res = -1
	for strat in [[2, 2, 3], [2, 3, 2], [3, 2, 2]]:
		ss = 0
		power = h
		eaten = 0
		for ii in range(n):
			if power <= a[ii]:
				while ss < len(strat):
					power *= strat[ss]
					ss += 1
					if power > a[ii]:
						break
			if power > a[ii]:
				power += a[ii] // 2
				eaten += 1
			else:
				break
		res = max(res, eaten)
	return res
T = read_int()[0]
for _ in range(T):
	(n, h) = read_int()
	a = read_int()
	a = sorted(a)
	print(solve(n, h, a))


def hunt(power, score):
	astro = astronauts[:len(astronauts) - score]
	while astro:
		prey = astro.pop()
		if power > prey:
			score += 1
			power += prey // 2
		else:
			break
	return (power, score)
num_of_cases = int(input())
blue = lambda loc: (dplist[loc[0] - 1][loc[1]][0] * 3, dplist[loc[0] - 1][loc[1]][1])
green = lambda loc: (dplist[loc[0]][loc[1] - 1][0] * 2, dplist[loc[0]][loc[1] - 1][1])
decide = lambda loc: sorted([hunt(*blue(loc)), hunt(*green(loc))], key=lambda t: (t[1], t[0]))[1]
for case in range(num_of_cases):
	h = int(input().split()[1])
	astronauts = list(map(int, input().split()))
	astronauts.sort(reverse=True)
	dplist = [[(0, 0) for j in range(4)] for i in range(3)]
	dplist[1][1] = hunt(h, 0)
	for i in range(1, 3):
		for j in range(1, 4):
			if i > 1 or j > 1:
				dplist[i][j] = decide((i, j))
	print(dplist[-1][-1][1])


t = int(input())

def solve():
	(n, h) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	x = h
	score1 = 0
	score2 = 0
	score3 = 0
	k = 0
	i = 0
	while i < n:
		if arr[i] < h:
			h += arr[i] // 2
			score1 += 1
			i += 1
		elif k == 0:
			h *= 2
			k += 1
		elif k == 1:
			h *= 2
			k += 1
		elif k == 2:
			h *= 3
			k += 1
		else:
			break
	i = 0
	k = 0
	h = x
	while i < n:
		if arr[i] < h:
			h += arr[i] // 2
			score2 += 1
			i += 1
		elif k == 0:
			h *= 3
			k += 1
		elif k == 1:
			h *= 2
			k += 1
		elif k == 2:
			h *= 2
			k += 1
		else:
			break
	i = 0
	k = 0
	h = x
	while i < n:
		if arr[i] < h:
			h += arr[i] // 2
			score3 += 1
			i += 1
		elif k == 0:
			h *= 2
			k += 1
		elif k == 1:
			h *= 3
			k += 1
		elif k == 2:
			h *= 2
			k += 1
		else:
			break
	print(max(score1, score2, score3))
while t:
	solve()
	t -= 1


def solve(n, h, arr, serium):
	arr.sort()
	green = 2
	blue = 1
	count = 0
	i = 0
	while i < n:
		if h <= arr[i]:
			if serium:
				h *= serium.pop()
			else:
				break
		else:
			h = h + arr[i] // 2
			i += 1
			count += 1
	return count
for _ in range(int(input())):
	(n, h) = map(int, input().split())
	li = list(map(int, input().split()))
	print(max(solve(n, h, li, [2, 2, 3]), solve(n, h, li, [2, 3, 2]), solve(n, h, li, [3, 2, 2])))
pass


T = int(input())
poss = ((2, 2, 3), (2, 3, 2), (3, 2, 2))
for _ in range(T):
	(n, rawh) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	m = []
	for s in poss:
		hum = 0
		ct = 0
		h = rawh
		for p in a:
			while h <= p and ct <= 2:
				h *= s[ct]
				ct += 1
			if h <= p and ct == 3:
				break
			h += p // 2
			hum += 1
		m.append(hum)
	print(max(m))


list1 = ((2, 2, 3), (2, 3, 2), (3, 2, 2))
for i in range(int(input())):
	(n, r) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	m = []
	for s in list1:
		hum = 0
		ct = 0
		h = r
		for p in a:
			while h <= p and ct <= 2:
				h *= s[ct]
				ct += 1
			if h <= p and ct == 3:
				break
			h += p // 2
			hum += 1
		m.append(hum)
	print(max(m))


import os
import math
import collections
import bisect
import functools
import itertools
import heapq
from collections import deque

def solve(a, n, h):
	a.sort()

	def f(i, h, s):
		while i < n:
			if h > a[i]:
				h += a[i] // 2
				i += 1
				continue
			if s:
				h *= s.pop()
			else:
				break
		return i
	return max(f(0, h, [3, 2, 2]), f(0, h, [2, 3, 2]), f(0, h, [2, 2, 3]))
t = int(input())
for _ in range(t):
	(n, h) = map(int, input().split())
	a = list(map(int, input().split()))
	print(solve(a, n, h))


test = int(input())
while test:
	test -= 1
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	a = sorted(a)
	ls = [[0, 1, 1], [1, 0, 1], [1, 1, 0]]
	mx = 0
	for x in ls:
		s = 0
		l = 0
		temp = m
		for i in a:
			while i >= temp:
				if l < 3:
					if x[l] == 1:
						temp *= 2
					else:
						temp *= 3
					l += 1
				if l == 3:
					break
			if i < temp:
				s += 1
				temp += i // 2
		mx = max(mx, s)
	print(mx)


t = int(input(''))
C = [0] * t
for i in range(t):
	LRX = input('').split(' ')
	n = int(LRX[0])
	h0 = int(LRX[1])
	A = sorted([int(x) for x in input('').split(' ')])
	s = 0
	for j in range(3):
		h = h0
		k = 0
		for z in range(4):
			while k < n and h > A[k]:
				h += A[k] // 2
				k += 1
			if z == j:
				h *= 3
			else:
				h *= 2
		s = max(s, k)
	C[i] = s
for j in C:
	print(j)


t = int(input())
for _ in range(t):
	(n, h0) = map(int, input().split())
	L = list(map(int, input().split()))
	L.sort()
	res = 0
	for ks in [[2, 2, 3], [2, 3, 2], [3, 2, 2]]:
		i = 0
		h = h0
		x = 0
		while i != n:
			if L[i] < h:
				h += L[i] // 2
				i += 1
			else:
				if x == 3:
					break
				h *= ks[x]
				x += 1
		res = max(res, i)
	print(res)


import math
import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
for _ in range(int(input())):
	(n, h) = invr()
	oarr = inlt()
	arr = [x for x in oarr if x != 1]
	checks = [[2, 2, 3, 0, h, 0, True], [2, 3, 2, 0, h, 0, True], [3, 2, 2, 0, h, 0, True]]
	arr.sort()
	for human in arr:
		for check in checks:
			if check[6]:
				if human >= check[4]:
					while human >= check[4]:
						if check[3] == 3:
							check[6] = False
							break
						check[4] *= check[check[3]]
						check[3] += 1
					if human < check[4]:
						check[5] += 1
						check[4] += human // 2
				else:
					check[5] += 1
					check[4] += human // 2
	i = 0
	for j in checks:
		i = max(i, j[5])
	print(i + oarr.count(1))


t = int(input())
for _ in range(t):
	(n, h) = map(int, input().split())
	nums = [int(x) for x in input().split()]
	nums.sort()
	h_start = h
	possible = [['g', 'g', 'b'], ['g', 'b', 'g'], ['b', 'g', 'g']]
	found = -1
	for order in possible:
		h = h_start
		serum = 0
		i = 0
		while i < n:
			if nums[i] < h:
				h += nums[i] // 2
				i += 1
			else:
				if serum == 3:
					break
				if order[serum] == 'g':
					h *= 2
				else:
					h *= 3
				serum += 1
		found = max(found, i)
	print(found)


tests = int(input())
for test in range(tests):
	pot = [[3, 2, 2], [2, 3, 2], [2, 2, 3]]
	(rangersCount, energy0) = map(int, input().split())
	rangers0 = list(map(int, input().split()))
	rangers0.sort()
	ans = [0, 0, 0]
	for i in pot:
		rangers = rangers0
		energy = energy0
		potions = i
		potion = 0
		rangerIndex = 0
		while rangerIndex < rangersCount:
			ranger = rangers[rangerIndex]
			if energy > ranger:
				energy += int(ranger / 2)
				rangerIndex += 1
			else:
				if potion == 3:
					break
				energy *= potions[potion]
				potion += 1
		ans.append(rangerIndex)
	print(max(ans))


for t in range(int(input())):
	(n, h) = map(int, input().split())
	lives = sorted(list(map(int, input().split())))
	powers = [2, 2, 3]
	ans1 = i = 0
	h1 = h
	while i < n:
		if lives[i] < h1:
			ans1 += 1
			h1 += lives[i] // 2
			i += 1
		elif powers:
			if powers.pop() == 3:
				h1 *= 3
			else:
				h1 *= 2
		else:
			break
	powers = [2, 3, 2]
	ans2 = i = 0
	h2 = h
	while i < n:
		if lives[i] < h2:
			ans2 += 1
			h2 += lives[i] // 2
			i += 1
		elif powers:
			if powers.pop() == 3:
				h2 *= 3
			else:
				h2 *= 2
		else:
			break
	powers = [3, 2, 2]
	ans3 = i = 0
	h3 = h
	while i < n:
		if lives[i] < h3:
			ans3 += 1
			h3 += lives[i] // 2
			i += 1
		elif powers:
			if powers.pop() == 3:
				h3 *= 3
			else:
				h3 *= 2
		else:
			break
	print(max(ans1, ans2, ans3))


t = int(input())
for i in range(t):
	(n, h) = map(int, input().split())
	a = sorted(list(map(int, input().split())))
	kill1 = 0
	kill2 = 0
	kill3 = 0
	j = 0
	s = [2, 2, 3]
	s2 = [2, 3, 2]
	si = 0
	xh = h
	while j < n:
		if h <= a[j]:
			if si < 3:
				h = h * s[si]
				si += 1
				if h > a[j]:
					h = h + a[j] // 2
					kill1 += 1
					j += 1
			else:
				break
		else:
			h = h + a[j] // 2
			kill1 += 1
			j += 1
	h = xh
	j = 0
	si = 2
	while j < n:
		if h <= a[j]:
			if si > -1:
				h = h * s[si]
				si -= 1
				if h > a[j]:
					h = h + a[j] // 2
					kill2 += 1
					j += 1
			else:
				break
		else:
			h = h + a[j] // 2
			kill2 += 1
			j += 1
	h = xh
	j = 0
	si = 0
	while j < n:
		if h <= a[j]:
			if si < 3:
				h = h * s2[si]
				si += 1
				if h > a[j]:
					h = h + a[j] // 2
					kill3 += 1
					j += 1
			else:
				break
		else:
			h = h + a[j] // 2
			kill3 += 1
			j += 1
	print(max(kill1, kill2, kill3))


t = int(input())
while t > 0:
	(n, h) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	a.sort()
	order = [3, 2, 2]
	case1 = h
	ans1 = 0
	for i in range(n):
		while case1 <= a[i] and len(order) > 0:
			case1 = case1 * order.pop()
		if case1 > a[i]:
			case1 = case1 + a[i] // 2
			ans1 += 1
		else:
			break
	order = [2, 3, 2]
	case2 = h
	ans2 = 0
	for i in range(n):
		while case2 <= a[i] and len(order) > 0:
			case2 = case2 * order.pop()
		if case2 > a[i]:
			case2 = case2 + a[i] // 2
			ans2 += 1
		else:
			break
	order = [2, 2, 3]
	case3 = h
	ans3 = 0
	for i in range(n):
		while case3 <= a[i] and len(order) > 0:
			case3 = case3 * order.pop()
		if case3 > a[i]:
			case3 = case3 + a[i] // 2
			ans3 += 1
		else:
			break
	print(max(max(ans1, ans2), ans3))
	t -= 1


T = int(input())
for _ in range(T):
	(N, H) = map(int, input().split())
	A = list(map(int, input().split()))
	A.sort()
	serum = [[2, 2, 3], [2, 3, 2], [3, 2, 2]]
	ans = 0
	for s in serum:
		h = H
		lans = 0
		si = 0
		ai = 0
		while True:
			a = A[ai]
			if a < h:
				h += a // 2
				lans += 1
				if lans == N:
					break
				ai += 1
			else:
				if si == 3:
					break
				h *= s[si]
				si += 1
		ans = max(ans, lans)
	print(ans)


from functools import lru_cache
import sys
import threading

def main():
	t = int(input())
	for _ in range(t):
		(n, h) = map(int, input().split())
		health = list(map(int, input().split()))
		health.sort()

		@lru_cache
		def dp(idx, h, g, b):
			if idx == n:
				return 0
			if h > health[idx]:
				return dp(idx + 1, h + health[idx] // 2, g, b) + 1
			res = 0
			if g:
				res = max(res, dp(idx, h * 2, g - 1, b))
			if b:
				res = max(res, dp(idx, h * 3, g, b - 1))
			return res
		print(dp(0, h, 2, 1))
sys.setrecursionlimit(1 << 30)
threading.stack_size(1 << 27)
main_thread = threading.Thread(target=main)
main_thread.start()
main_thread.join()


t = int(input())
for _ in range(t):
	(n, h) = map(int, input().split())
	L0 = list(map(int, input().split()))
	L = sorted(L0)
	count = 0
	for l in range(3):
		H = h
		ct = 0
		i0 = 0
		for p in range(4):
			while i0 < n and L[i0] < H:
				H += L[i0] // 2
				ct += 1
				i0 += 1
			if p == l:
				H *= 3
			else:
				H *= 2
		count = max(count, ct)
	print(count)


for i in range(int(input())):
	(n, h) = map(int, input().split())
	a = [int(x) for x in input().split()]
	a.sort()
	q = [[2, 2, 3], [2, 3, 2], [3, 2, 2]]
	maxAns = 0
	for j in range(3):
		index = 0
		tempH = h
		ans = 0
		k = 0
		while k < n:
			if a[k] < tempH:
				tempH += a[k] // 2
				ans += 1
				k += 1
			else:
				if index == 3:
					break
				tempH *= q[j][index]
				index += 1
		maxAns = max(ans, maxAns)
	print(maxAns)


t = int(input())
for i in range(t):
	(n, h) = map(int, input().split())
	a = [int(x) for x in input().split()]
	a.sort()
	number = 0
	for i in range(3):
		h0 = 0
		num = 0
		serum = 3
		h1 = h
		while h0 < n and serum >= 0:
			if a[h0] < h1:
				num += 1
				h1 += int(a[h0]) // 2
				h0 += 1
				continue
			if a[h0] >= h1:
				if serum == i + 1:
					h1 = 3 * h1
					serum -= 1
					continue
				else:
					h1 = 2 * h1
					serum -= 1
					continue
		number = max(num, number)
	print(number)


import sys
sys.setrecursionlimit(10 ** 7)
from heapq import heappop, heappush
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
from itertools import product, combinations, permutations
from math import sin, cos
ipt = sys.stdin.readline
iin = lambda : int(ipt())
lmin = lambda : list(map(int, ipt().split()))
for _ in range(iin()):
	(N, H) = lmin()
	A = lmin()
	A.sort()
	ma = 0
	for p in permutations((2, 2, 3), 3):
		q = list(p)
		h = H
		ans = 0
		for i in range(N):
			if h > A[i]:
				h += A[i] // 2
			else:
				while q and h <= A[i]:
					h *= q.pop()
				if not q and h <= A[i]:
					ans = i
					break
				h += A[i] // 2
		else:
			ans = N
		ma = max(ma, ans)
	print(ma)


import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(200000)
for _ in range(int(input())):
	(N, H) = map(int, input().split())
	A = list(map(int, input().split()))
	A.sort()
	v = [(0, 2, 1, H, 0)]
	ans = 0
	while v:
		(idx, green, blue, power, cnt) = v.pop()
		ans = max(ans, cnt)
		if idx >= N:
			continue
		if power > A[idx]:
			v.append((idx + 1, green, blue, power + A[idx] // 2, cnt + 1))
		else:
			if green > 0 and power * 2 > A[idx]:
				v.append((idx + 1, green - 1, blue, power * 2 + A[idx] // 2, cnt + 1))
			if green > 1 and power * 4 > A[idx]:
				v.append((idx + 1, green - 2, blue, power * 4 + A[idx] // 2, cnt + 1))
			if blue > 0 and power * 3 > A[idx]:
				v.append((idx + 1, green, 0, power * 3 + A[idx] // 2, cnt + 1))
			if green and blue and (power * 6 > A[idx]):
				v.append((idx + 1, green - 1, 0, power * 6 + A[idx] // 2, cnt + 1))
			if green == 2 and blue and (power * 12 > A[idx]):
				v.append((idx + 1, 0, 0, power * 12 + A[idx] // 2, cnt + 1))
	print(ans)