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

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)
# cook your dish here


# cook your dish here
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
  else: 
   if i<=2*s and m>=2:
    c+=1
    m-=2
 print(c)

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
  else: 
   if 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 = list(map(int, input().split()))
 arr2 = list(map(int, input().split()))
 count = 0
 arr2.sort()
 arr3 = arr2.copy()
 count2 = 0
 for k in arr3:
  if k > s * 2:
   arr2.remove(k)
 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):
   #print(arr[i])
   m-=1
   count+=1
  else:
   if(arr[i]%s==0):
    if(arr[i]//s<=2):
     #print(arr[i])
     m=m-(arr[i]//s)
     count+=1
   else:
    if((arr[i]//s+1)<=2):
     #print(arr[i])
     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
  else:
   if(arr[i]%s==0):
    if(arr[i]//s<=m):
     m=m-(arr[i]//s)
     count+=1
   else:
    if((arr[i]//s+1)<=m):
     m=m-(arr[i]//s+1)
     count+=1
  i+=1
 print(count)

# cook your dish here
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 = (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)


# cook your dish here
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)

# cook your dish here
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)

# cook your dish here
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)

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
 n,m,s=list(map(int,input().split(" ")))
 h=list(map(int,input().split( )))
 h1=list(h)
 
 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)
  
  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
 n,m,s=list(map(int,input().split(" ")))
 h=list(map(int,input().split( )))
 h1=list(h)
 
 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)
  elif len(t)-count<1:
   print(count)
  else:
   print(count+(m-count)//2)



T=int(input())
for i in range(0,T):
 t=[]
 count=0
 n,m,s=list(map(int,input().split(" ")))
 h=list(map(int,input().split( )))
 h1=list(h)
 
 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)
  elif len(t)-count<1:
   print(len(t))
  else:
   print(count+(m-count)//2)



T=int(input())
for i in range(0,T):
 t=[]
 count=0
 n,m,s=list(map(int,input().split(" ")))
 h=list(map(int,input().split( )))
 h1=list(h)
 
 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)
  elif len(t)-count==0:
   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)


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)

 
 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)


# cook your dish here
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))


# cook your dish here
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())))
 #print(l)
 for i in l:
  k=((i-1)//h)+1
  if k<3:
   
   u+=k
   #print(u)
   if u>d:
    break
   else:
    nch+=1
  else:
   break
 print(nch)
 #print(u)


# cook your dish here
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)


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*2:
   count+=1
   if i<=s:
    m-=1
   else:
    m-=2
   if m==0:
    break
   elif m==-1:
    count-=1
    break
 print(count)


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