Chef wants to impress Chefina by giving her the maximum number of gifts possible.

Chef is in a gift shop having N items where the cost of the i^{th} item is equal to A_{i}.
Chef has K amount of money and a 50 \% off discount coupon that he can use for at most one of the items he buys.

If the cost of an item is equal to X, then, after applying the coupon on that item, Chef only has to pay {\bf \lceil \frac{X}{2} \right\rceil} (rounded up to the nearest integer) amount for that item.

Help Chef find the maximum number of items he can buy with K amount of money and a 50 \% discount coupon given that he can use the coupon on at most one item.

------ Input Format ------ 

- The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
- The first line of each test case contains two space-separated integers N and K.
- The next line contains N space-separated integers, where the i^{th} integer A_{i} denotes the cost of the i^{th} item.

------ Output Format ------ 

For each test case, print a single line containing one integer ― the maximum number of items Chef can buy.

------ Constraints ------ 

$1 ≤ T ≤ 10^{3}$
$1 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{9}$
$0 ≤ K ≤ 10^{9}$
- Sum of $N$ over all test cases does not exceed $2\cdot10^{5}$.

----- Sample Input 1 ------ 
3
1 4
5
3 15
4 4 5
3 10
6 7 4
----- Sample Output 1 ------ 
1
3
2
----- explanation 1 ------ 
Test case $1$: After applying the discount, Chef can buy the only available item at ${\lceil \frac{5}{2} \right\rceil} = 3$.

Test case $2$: Chef can buy all three items even without using the coupon.

Test case $3$: After applying coupon on the third item, Chef can buy the second and the third item at $7 + {\lceil \frac{4}{2} \right\rceil} = $ $ 7 + 2 = 9$.  
It is not possible for Chef to buy more than two items.

Source: codechef | Difficulty: EASY
Tags: Sorting


Solutions:
def JANU(N):
	if N & 1:
		return N // 2 + 1
	else:
		return N // 2
Raji = print
T = int(input())
for i in range(T):
	Sum = 0
	count = 0
	(N, K) = map(int, input().split())
	L = list(map(int, input().split()))
	L.sort()
	for i in range(N):
		Sum = Sum + L[i]
		count = count + 1
		if i == N - 1 and Sum <= K:
			print(count)
			break
		elif Sum > K and Sum - L[i] + JANU(L[i]) > K:
			Raji(count - 1)
			break
		elif Sum > K and Sum - L[i] + JANU(L[i]) <= K:
			Raji(count)
			break


from math import ceil
T = int(input())
for i in range(T):
	(n, money) = map(int, input().split())
	costs = list(map(int, input().split()))
	if sum(costs) <= money:
		print(n)
	elif n == 1:
		if ceil(costs[0] / 2) <= money:
			print(1)
		else:
			print(0)
	else:
		costs.sort()
		cost = 0
		idx = 0
		while idx < n:
			if cost + costs[idx] <= money:
				cost += costs[idx]
				idx += 1
			else:
				if cost + ceil(costs[idx] / 2) <= money:
					idx += 1
				break
		print(idx)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	summ = 0
	count = -1
	for j in a:
		summ += j
		count += 1
		if summ > k:
			break
	if summ - a[count] / 2 <= k:
		print(count + 1)
	else:
		print(count)


from math import ceil
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	p = sorted([int(x) for x in input().split()])
	(s, ans) = (0, 0)
	for i in p:
		if s + i <= b:
			s += i
			ans += 1
		else:
			if s + ceil(i / 2) <= b:
				ans += 1
			break
	print(ans)


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))[:n]
	if sum(l) <= k:
		print(n)
	elif n == 1:
		if l[0] / 2 <= k:
			print(1)
		else:
			print(0)
	else:
		l = sorted(l)
		c = 0
		idx = 0
		while idx <= n:
			if c + l[idx] <= k:
				c += l[idx]
				idx += 1
			else:
				if c + math.ceil(l[idx] / 2) <= k:
					c += l[idx]
					idx += 1
				break
		print(idx)


for t in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	c = 0
	for i in range(n):
		k -= a[i]
		if k >= 0:
			c += 1
		else:
			k += a[i] // 2
			if k >= 0:
				c += 1
				break
			else:
				break
	print(c)


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = sorted(list(map(int, input().split())))
	c = 0
	for i in a:
		if k - i < 0 and 0 < k >= math.ceil(i / 2):
			c += 1
			break
		elif k >= i:
			k -= i
			c += 1
	print(c)


for _ in range(int(input())):
	(gift, money) = map(int, input().split())
	prices = list(map(int, input().split()))
	prices.sort()
	bought = 0
	coupon = 1
	for price in prices:
		if money >= price:
			money -= price
			bought += 1
		elif coupon == 1 and money >= price / 2:
			coupon = 0
			money -= price / 2
			bought += 1
	print(bought)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	L = sorted(list(map(int, input().strip().split())))
	y = 0
	while k > 0 and y <= len(L) - 1:
		k = k - L[y]
		if k < 0:
			k = k + L[y]
			dis = int(L[y] / 2)
			if k >= L[y] - dis:
				y += 1
			break
		y += 1
	print(y)


import math
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	m1 = min(a)
	m2 = max(a)
	s1 = sum(a)
	if n == 1 and math.ceil(a[0] / 2) <= k:
		print(1)
	elif s1 < k:
		print(n)
	else:
		a.sort()
		s1 = 0
		c = 0
		for j in range(n):
			s1 = s1 + a[j]
			if s1 < k:
				c = c + 1
			elif s1 - a[j] + math.ceil(a[j] / 2) <= k:
				c = c + 1
			else:
				break
		print(c)


t = int(input())
for i in range(t):
	(n, k) = list(map(int, input().split(' ')))
	a = list(map(int, input().split()))
	if sum(a) <= k:
		print(n)
	else:
		a = sorted(a)
		sum1 = 0
		sum2 = 0
		pos1 = 0
		pos2 = 0
		for ele in a:
			if sum1 + ele / 2 <= k:
				pos1 += 1
				sum1 += ele
		print(max(pos1, pos2))


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	(count, flag) = (0, 1)
	for i in arr:
		if k > 0:
			if k - i >= 0:
				count += 1
				k -= i
			elif flag == 1:
				if k - math.ceil(i / 2) >= 0:
					count += 1
					k -= math.ceil(i / 2)
					flag = 0
		else:
			break
	print(count)


from math import *
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = [int(x) for x in input().split()]
	a.sort()
	c = 1
	count = 0
	for i in range(n):
		if k - a[i] >= 0:
			count += 1
			k -= a[i]
		elif k - ceil(a[i]) / 2 >= 0 and c == 1:
			count += 1
			k -= ceil(a[i] / 2)
			c = 0
		else:
			break
	print(count)


from math import *
for t in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	rnum = 0
	count = 0
	for i in range(n):
		if arr[i] < k:
			rnum += 1
			k = k - arr[i]
		elif arr[i] >= k and ceil(arr[i] / 2) <= k:
			rnum += 1
			count = 1
			print(rnum)
			break
	if count == 0:
		print(rnum)


import math
T = int(input())
for _ in range(0, T):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	g = 0
	a = sorted(a)
	i = 0
	while True:
		if i >= n:
			break
		if k >= a[i]:
			k -= a[i]
			i += 1
		else:
			if k >= math.ceil(a[i] / 2):
				k -= math.ceil(a[i] / 2)
				i += 1
			break
	print(i)


import math
tc = int(input())
for _ in range(tc):
	(n, k) = [int(x) for x in input().split()]
	arr = [int(x) for x in input().split()]
	arr.sort()
	i = 0
	moneyleft = k
	while True:
		if i >= n:
			break
		if moneyleft >= arr[i]:
			moneyleft -= arr[i]
			i += 1
		else:
			if moneyleft >= math.ceil(arr[i] / 2):
				moneyleft -= math.ceil(arr[i] / 2)
				i += 1
			break
	print(i)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	sumv = 0
	count = 0
	for (i, e) in enumerate(a):
		if sumv + e <= k:
			sumv += e
			count += 1
		else:
			if sumv + (e + 1) // 2 <= k:
				print(count + 1)
			else:
				print(count)
			break
	else:
		print(count)


from collections import *
from math import *
from sys import *
T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split())
	A = list(map(int, input().split()))
	A.sort()
	val = 0
	cnt = 0
	for i in A:
		if val + i <= M:
			val += i
			cnt += 1
		else:
			if i % 2:
				if val + i // 2 + 1 <= M:
					cnt += 1
			elif val + i // 2 <= M:
				cnt += 1
			break
	print(cnt)


for i in range(int(input())):
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	A.sort()
	a = 0
	t = 0
	for j in A:
		if K < j:
			j = j - int(j / 2)
			if K >= j:
				K = K - j
				t = t + 1
		if K >= j:
			K = K - j
			t = t + 1
	print(t)


def quicksort(L, l, r):
	if r - l <= 1:
		return L
	(pivot, lower, upper) = (l, l + 1, l + 1)
	for i in range(l + 1, r):
		if L[i] > L[pivot]:
			upper += 1
		else:
			(L[i], L[lower]) = (L[lower], L[i])
			lower += 1
			upper += 1
	(L[l], L[lower - 1]) = (L[lower - 1], L[l])
	lower = lower - 1
	quicksort(L, l, lower)
	quicksort(L, lower + 1, r)
	return L
t = int(input())
for i in range(t):
	n = list(map(int, input().split(' ')))
	l = list(map(int, input().split(' ')))
	if sum(l) <= n[1]:
		print(n[0])
	else:
		L = quicksort(l, 0, n[0])
		(s, count, cycle) = (0, 0, 0)
		for m in L:
			s += m
			count += 1
			if s > n[1]:
				s -= m / 2
				cycle += 1
				if s <= n[1]:
					cycle += 1
				else:
					count -= 1
					break
		print(count)


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	(sum, cnt) = (0, 0)
	for i in l:
		if sum + i > k:
			v = math.ceil(i / 2)
			if sum + v <= k:
				sum = sum + v
				cnt = cnt + 1
		elif sum + i <= k:
			sum = sum + i
			cnt = cnt + 1
		else:
			break
	print(cnt)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	res = 0
	coupon = 1
	l.sort()
	for i in range(n):
		if l[i] <= k:
			k -= l[i]
			res += 1
		elif l[i] / 2 <= k:
			a = round(l[i] / 2)
			k -= a
			res += 1
			coupon = 0
	print(res)


t = input()
for c in range(0, int(t)):
	(n, k) = input().split()
	a = input().split()
	arr = []
	for x in a:
		arr.append(int(x))
	arr.sort()
	count = 0
	k = int(k)
	for y in range(0, int(n)):
		if arr[y] <= k:
			k = k - arr[y]
			count = count + 1
		elif arr[y] / 2 <= k:
			k = k - arr[y] / 2
			count = count + 1
	print(count)


for _ in range(int(input())):
	(n, j) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	s = 0
	d = 0
	for _ in range(n):
		d += l[_]
		s = d
		if s > j:
			s -= l[_] // 2
			if s <= j:
				print(_ + 1)
				break
			else:
				print(_)
				break
	if d <= j:
		print(n)


for i in range(int(input())):
	(n, k) = map(int, input().split(' '))
	li = list(map(int, input().split(' ')))
	li.sort()
	(sum, count) = (0, 0)
	for i in li:
		sum += i
		if sum <= k:
			count += 1
		elif sum - i // 2 <= k:
			count += 1
			break
		else:
			break
	print(count)


n = int(input())
for i in range(n):
	(x, y) = (int(i) for i in input().split())
	l = list(map(int, input().split()))
	l.sort()
	count = 0
	for i in range(x):
		if y >= l[i]:
			y -= l[i]
			count = count + 1
		elif y - (l[i] + 1) // 2 >= 0:
			count = count + 1
			break
		else:
			break
	print(count)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	li = sorted(list(map(int, input().split())))
	cnt = 0
	for i in li:
		if k - i >= 0:
			k -= i
			cnt += 1
		elif k - -(i // -2) >= 0:
			cnt += 1
			break
		else:
			break
	print(cnt)


import math

def gift(n: int, k: int, arr: list):
	s = 0
	cnt = 0
	arr.sort()
	for i in range(n):
		ele = math.ceil(arr[i] / 2)
		if s + ele <= k:
			cnt += 1
			s += arr[i]
		else:
			break
	return cnt
t = int(input())
while t:
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	print(gift(n, k, arr))
	t -= 1


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	inp = list(map(int, input().split()))
	inp = sorted(inp)
	cnt = 0
	buy = []
	for i in range(n):
		if inp[i] < k:
			k -= inp[i]
			cnt += 1
		elif inp[i] / 2 <= k:
			cnt += 1
			break
	print(cnt)


for x in range(int(input())):
	(n, k) = [int(d) for d in input().split()]
	a = [int(d) for d in input().split()]
	a.sort()
	count = 0
	for i in range(n):
		if a[i] < k:
			k -= a[i]
			count += 1
		elif a[i] / 2 <= k:
			count += 1
			break
	print(count)


t = int(input())
for _ in range(t):
	(N, k) = map(int, input().split())
	a = [int(x) for x in input().split()]
	l = sorted(a)
	count = 0
	for i in range(len(l)):
		if l[i] < k:
			count += 1
			k = k - l[i]
		else:
			if l[i] / 2 <= k:
				count += 1
			break
	print(count)


tests = int(input())
for i in range(tests):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	ans = 0
	for j in arr:
		if j <= k:
			k -= j
			ans += 1
		elif j / 2 <= k:
			ans += 1
			break
	print(ans)


import math
T = int(input())
for _ in range(T):
	(N, K) = map(int, input().split())
	lst = list(map(int, input().split()))
	if sum(lst) <= K:
		print(N)
	else:
		lst.sort()
		ans = 0
		for i in range(N):
			if ans + lst[i] < K:
				ans = ans + lst[i]
			elif ans + lst[i] == K:
				break
			else:
				if ans + math.ceil(lst[i] / 2) <= K:
					pass
				else:
					i -= 1
				break
		print(i + 1)


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	c = 0
	for i in a:
		if i <= k:
			c += 1
			k -= i
		else:
			if math.ceil(i / 2) <= k:
				c += 1
			break
	print(c)


for _ in range(int(input())):
	(n, k) = map(int, input().split(' '))
	A = list(map(int, input().split(' ')))
	A.sort()
	spent = 0
	for (i, a) in enumerate(A):
		spent += a
		if spent >= k:
			break
	else:
		print(n)
		continue
	if i <= n - 1:
		spent = spent - a
		if spent + (a + 1) // 2 <= k:
			print(i + 1)
		else:
			print(i)


for _ in range(int(input())):
	(n, k) = map(int, input().split(' '))
	a = list(map(int, input().split(' ')))
	a.sort()
	sum = 0
	i = 0
	while i < len(a):
		sum += a[i]
		if sum >= k:
			break
		i += 1
	if i == n:
		print(n)
	else:
		sum = sum - a[i]
		if sum + (a[i] + 1) // 2 <= k:
			print(i + 1)
		else:
			print(i)


import math

def solve():
	(n, k) = map(int, input().split())
	cost = map(int, input().split())
	cost = sorted(cost)
	res = 0
	temp_cost = k
	for i in range(n):
		if cost[i] <= temp_cost:
			res += 1
			temp_cost -= cost[i]
		elif math.ceil(cost[i] / 2) <= temp_cost:
			res += 1
			temp_cost -= math.ceil(cost[i] / 2)
			break
	print(res)
tc = int(input())
while tc:
	solve()
	tc -= 1


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(sorted(map(int, input().split())))
	s = 0
	for i in l:
		if i <= k:
			s += 1
			k -= i
		else:
			if math.ceil(i / 2) <= k:
				s += 1
			break
	print(s)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().lstrip().split()))
	arr.sort()
	add = 0
	count = 0
	import math
	if sum(arr) <= k:
		count += n
	else:
		for i in range(n):
			add += arr[i]
			if add >= k:
				add -= arr[i]
				add += math.ceil(arr[i] / 2)
				if add <= k:
					count += 1
				break
			else:
				count += 1
	print(count)


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	A.sort()
	i = 0
	total = 0
	if K == 0:
		print(0)
		continue
	while total < K and i < N:
		total += A[i]
		i += 1
	if total - A[i - 1] // 2 <= K:
		i += 1
	print(i - 1)


import math
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	cities = list(map(int, input().split()))
	cities.sort()
	count = 0
	for i in range(n):
		if cities[i] <= k:
			k = k - cities[i]
			count += 1
		elif math.ceil(cities[i] / 2) <= k:
			count += 1
			break
	print(count)


def sol(a, k):
	a.sort()
	for i in range(len(a)):
		if a[i] <= k:
			k -= a[i]
		elif (a[i] + 1) // 2 <= k:
			return i + 1
		else:
			return i
	return len(a)
for tc in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	print(sol(a, k))


import math
t = int(input())
for i in range(t):
	[N, K] = [int(i) for i in input().split()]
	arr = [int(i) for i in input().split()]
	arr.sort()
	items = 0
	cost = 0
	for i in range(N):
		if cost + arr[i] <= K:
			cost += arr[i]
			items += 1
		elif cost + math.ceil(arr[i] / 2) <= K:
			cost += math.ceil(arr[i] / 2)
			items += 1
			break
		else:
			break
	print(items)


import math
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	l = [int(i) for i in input().split()]
	l.sort()
	cost = 0
	i = 0
	while i < n and cost + l[i] <= k:
		cost += l[i]
		i += 1
	if i < n and math.ceil(cost + l[i] / 2) <= k:
		print(i + 1)
	else:
		print(i)


def solve(n, k, cost):
	cost.sort()
	cnt = 0
	for c in cost:
		if c <= k:
			k -= c
			cnt += 1
		else:
			dc = c // 2 + 1 if c % 2 else c // 2
			if dc <= k:
				cnt += 1
			break
	return cnt
t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().split()))
	cost = list(map(int, input().split()))
	print(solve(n, k, cost))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	sm = 0
	ans = n
	a.sort()
	for i in range(len(a)):
		if sm + (a[i] + 1) // 2 > k:
			ans = i
			break
		sm += a[i]
	print(ans)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	c = a = s = flag = 0
	for j in range(n):
		s = s + l[j]
		c = j
		if s > k:
			a = l[j]
			c = j
			flag = 1
			break
	if flag == 1:
		if s - a / 2 <= k:
			print(c + 1)
		else:
			print(c)
	else:
		print(c + 1)


t = int(input())
while t:
	t = t - 1
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	l = sorted(a)
	count = 0
	for i in range(len(l)):
		if l[i] <= k:
			k = k - l[i]
			count = count + 1
		else:
			if l[i] / 2 <= k:
				count = count + 1
			break
	print(count)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = [int(i) for i in input().split()]
	arr.sort()
	count = 0
	exp = 0
	for i in range(n):
		exp += arr[i]
		if exp <= k:
			count += 1
		if exp > k:
			exp = exp - arr[i] + arr[i] / 2
			if exp <= k:
				count += 1
				break
	print(count)


import math
T = int(input())
for _ in range(T):
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	A.sort()
	res = 0
	for i in A:
		if K > i:
			res += 1
			K -= i
		else:
			if math.ceil(i / 2) <= K:
				res += 1
			break
	print(res)


t = int(input())
for i in range(t):
	(n, k) = [eval(x) for x in input().split()]
	a = [eval(x) for x in input().split()]
	sum = 0
	a.sort()
	count = 0
	for x in a:
		if x <= k - sum:
			sum += x
			count += 1
		else:
			break
	if k - sum == 0:
		print(count)
	elif count < n and a[count] / 2 <= k - sum:
		print(count + 1)
	else:
		print(count)


def div_mod(n, k, l):
	new_l = sorted(l)
	sums = 0
	a = 0
	if n == 1:
		if l[0] <= k or l[0] / 2 <= k:
			return 1
		else:
			return 0
	for i in range(n):
		sums += new_l[i]
		if sums <= k:
			a += 1
			continue
		else:
			sums -= new_l[i]
			sums += new_l[i] / 2
			if sums <= k:
				a += 1
			break
	return a

def main():
	g = int(input())
	for i in range(g):
		(n, k) = map(int, input().split())
		l = list(map(int, input().split()))
		print(div_mod(n, k, l))
main()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	i = 0
	while i < n and k > arr[i]:
		k -= arr[i]
		i += 1
	if i < n and arr[i] // 2 + arr[i] % 2 <= k:
		i += 1
	print(i)


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	lst = list(map(int, input().split()))
	if sum(lst) <= k:
		print(n)
	else:
		lst.sort()
		ans = 0
		for i in range(n):
			if ans + lst[i] < k:
				ans = ans + lst[i]
			elif ans + lst[i] == k:
				break
			else:
				if ans + math.ceil(lst[i] / 2) <= k:
					pass
				else:
					i -= 1
				break
		print(i + 1)


t = int(input())
while t > 0:
	(n, k) = input().split(' ')
	n = int(n)
	k = int(k)
	a = list(map(int, input().split()))
	a = sorted(a)
	items = 0
	for i in range(0, n):
		if k > a[i]:
			k = k - a[i]
			items = items + 1
		else:
			if k * 2 >= a[i]:
				items += 1
			break
	print(items)
	t = t - 1


t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	items = list(map(int, input().split()))
	items.sort()
	count = 0
	for i in items:
		if k > i:
			k -= i
			count = count + 1
		else:
			if k * 2 >= i:
				count += 1
			break
	print(count)
	t -= 1