ZCO is approaching, and you want to be well prepared!  
There are $N$ topics to cover and the $i^{th}$ topic takes $H_i$ hours to prepare (where $1 \le i \le N$). You have only $M$ days left to prepare, and you want to utilise this time wisely. You know that you can't spend more than $S$ hours in a day preparing, as you get tired after that. You don't want to study more than one topic in a day, and also, don't want to spend more than two days on any topic, as you feel that this is inefficient.  
Given these constraints, can you find the maximum number of topics you can prepare, if you choose the topics wisely?

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- The first line of each test case contains three space-separated integers: $N$, $M$ and $S$, denoting the number of topics, the number of days remaining and the number of hours you can study in a day.  
- The second line of each test case contains $N$ space-separated integers $H_i$, denoting the number of hours needed to prepare for the $i^{th}$ topic.

-----Output:-----
For each testcase, output in a single line: the maximum number of topics you can prepare.

-----Constraints-----
- $1 \leq T \leq 10$
- $1 \leq N \leq 10^5$
- $1 \leq M \leq 10^5$
- $1 \leq S \leq 16$
- $1 \leq H_i \leq 50$

-----Subtasks-----
- 30 points : Every topic takes the same number of hours to prepare (i.e. all $H_i$ are equal).
- 70 points : Original constraints.

-----Sample Input:-----
2
5 4 10
10 24 30 19 40
5 4 16
7 16 35 10 15

-----Sample Output:-----
2
4

-----Explanation:-----
Testcase 1:

You can choose topics $1$ and $4$. Topic $1$ will consume a single day , while topic $4$ will consume two days.  Thus, you'll be able to prepare these two topics within the 4 remaining days. But you can check that you cannot do any better.
Testcase 2:

You can choose topics $1$, $2$, $4$, and $5$. Each of them will consume one day each. Thus you'll be able to cover $4$ topics.

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
import math
T = int(input())
for i in range(T):
	(N, M, S) = input().split()
	N = int(N)
	M = int(M)
	S = int(S)
	ls = list(map(int, input().split()))
	maxx = max(ls)
	if S < 17 and maxx <= 50:
		ls.sort()
		total_sum = M * S
		count = 0
		sum = 0
		for i in ls:
			if i / S > 2:
				continue
			else:
				sum = sum + math.ceil(i / S) * S
				if sum <= total_sum:
					count = count + 1
		print(count)


for _ in range(int(input())):
	(n, m, s) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	arr.sort()
	count = 0
	for a in arr:
		if a <= s and m >= 1:
			count += 1
			m -= 1
		elif a <= 2 * s and m >= 2:
			count += 1
			m -= 2
	print(count)


for _ in range(int(input())):
	(n, m, s) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	x = m * s
	c = 0
	for i in l:
		if i <= s and m >= 1:
			c += 1
			m -= 1
		elif i <= 2 * s and m >= 2:
			c += 1
			m -= 2
	print(c)


for _ in range(int(input())):
	(n, m, s) = list(map(int, input().split()))
	arr2 = list(map(int, input().split()))
	count = 0
	arr2.sort()
	j = n
	arr3 = arr2.copy()
	count2 = 0
	for k in range(len(arr3)):
		if arr3[k] > s * 2:
			j = k
			break
	arr2 = arr2[:j]
	for kk in arr2:
		if count >= m:
			break
		elif kk <= s:
			count += 1
			count2 += 1
		else:
			count += 2
			count2 += 1
	if count <= m:
		print(count2)
	else:
		print(count2 - 1)


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


for _ in range(int(input())):
	(n, m, s) = (int(i) for i in input().split())
	li = list((int(i) for i in input().split()))
	c = 0
	d = m
	for i in li:
		if i <= s:
			c += 1
			d -= 1
	if m <= c:
		print(m)
	else:
		for i in li:
			if d < 2:
				break
			if i > s and i <= 2 * s:
				c += 1
				d -= 2
		print(c)


for _ in range(int(input())):
	(n, m, s) = map(int, input().split())
	ls = list(map(int, input().split()))
	ls.sort()
	ans = 0
	for i in range(n):
		if ls[i] <= s:
			if m > 0:
				ans += 1
				m -= 1
			else:
				break
		elif ls[i] <= 2 * s:
			if m > 1:
				ans += 1
				m -= 2
			else:
				break
		else:
			break
	print(ans)


for i in range(int(input())):
	(n, m, s) = map(int, input().split(' '))
	(h1, t, count) = (list(map(int, input().split())), [], 0)
	t = [x for x in h1 if x <= 2 * s]
	if len(t) == 0:
		print(0)
	else:
		count = sum(map(lambda x: x <= s, t))
		if count >= m:
			print(m)
		elif m >= count + (len(t) - count) * 2:
			print(len(t))
		else:
			print(count + (m - count) // 2)


T = int(input())
for i in range(0, T):
	t = []
	count = 0
	a = input().split(' ')
	n = int(a[0])
	m = int(a[1])
	s = int(a[2])
	h = list(map(int, input().split(' ')))
	h1 = list(h)
	h1.sort()
	t = [x for x in h1 if x <= 2 * s]
	if len(t) == 0:
		print(0)
	else:
		count = sum([x <= s for x in t])
		if count >= m:
			print(m)
		else:
			print(count + (m - count) // 2)


import math
no_of_test_cases = int(input())

def maxTopics(hours, N, M, S):
	sorted_hours = sorted(hours)
	no_of_days_needed = []
	for x in sorted_hours:
		if math.ceil(x / S) <= 2:
			no_of_days_needed.append(math.ceil(x / S))
	no_of_topics_coverd = 0
	for x in no_of_days_needed:
		if M - x >= 0:
			no_of_topics_coverd += 1
			M = M - x
	return no_of_topics_coverd
for x in range(1, no_of_test_cases + 1):
	(N, M, S) = input().split(' ')
	N = int(N)
	M = int(M)
	S = int(S)
	hours = list([int(x) for x in input().split(' ')])
	print(maxTopics(hours, N, M, S))


t = int(input())
for q in range(t):
	u = 0
	nch = 0
	(ch, d, h) = list(map(int, input().split()))
	l = sorted(list(map(int, input().split())))
	for i in l:
		k = (i - 1) // h + 1
		if k < 3:
			u += k
			if u > d:
				break
			else:
				nch += 1
		else:
			break
	print(nch)


import math
x = int(input())
for i in range(x):
	(a, b, c) = map(int, input().strip().split())
	s = [int(i) for i in input().strip().split()]
	s.sort()
	m = 0
	counter = 0
	for i in range(a):
		a1 = math.ceil(s[i] / c)
		if b >= a1 and a1 <= 2:
			counter += 1
			b = b - a1
		else:
			break
	print(counter)


for _ in range(int(input())):
	(n, m, s) = [int(x) for x in input().split()]
	h = list(map(int, input().split()))
	h.sort()
	sum = 0
	count = 0
	for i in h:
		if i <= s and m > 0:
			m -= 1
			count += 1
		elif i <= s * 2 and m > 1:
			m -= 2
			count += 1
		if m == 0:
			break
	print(count)