Lumpy is a bus driver. Today, the conductor is absent so Lumpy has to do the conductor's job as well. There are N creatures in the bus. Sometimes the creatures don't carry change and can't pay the exact amount of the fare. Each creature in the bus today has paid an amount
greater than his/her fare. You are given information about the extra amount paid by each creature, by an array A of size N, where Ai denotes the extra amount paid by the i-th creature, in rupees.
After the end of the trip, Lumpy noticed that he had P one rupee coins and Q two rupee coins. He wants to pay back the creatures using this money. Being a kind hearted moose, Lumpy wants to pay back as many creatures as he can. Note that Lumpy will 
not pay back the i-th creature if he can't pay the exact amount that the i-th creature requires with the coins that he possesses. 
Lumpy is busy driving the bus and doesn't want to calculate the maximum number of creatures he can satisfy - He will surely cause an accident if he tries to do so. Can you help him out with this task? 

-----Input-----
- The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
- For each test case, first line consists of three space separated integers N, P and Q.
- Second line consists of N space separated integers A containing N space integers, where i-th integer denotes Ai.

-----Output-----
- For each test case, output a single line containing an integer corresponding to maximum number of creatures that Lumpy can pay back.

-----Constraints-----
- 1 ≤ T ≤ 106
- 1 ≤ N ≤ 105
- 1 ≤ Ai ≤ 109
- 0 ≤ P, Q ≤ 1014
- Sum of N over all the cases does not exceed 106

-----Subtasks-----
- Subtask #1 (15 points): P = 0
- Subtask #2 (15 points): Q = 0
- Subtask #3 (70 points): Original constraints

-----Example-----
Input:3
3 3 0
1 2 2
3 2 1
1 2 1
4 5 4
2 3 4 5

Output:2
3
3

-----Explanation-----
Example 1. Lumpy has just 3 one rupee coins. 

He can pay creatures numbered {1, 2} or creatures numbered {1, 3} with these coins. Thus, answer is 2. 
Example 2. Lumpy has 2 one rupee coins and 1 two rupee coin. 

In the optimal solution, Lumpy can give the two rupee coin to creature 2 and the one rupee coins to creatures 1 and 3. Thus, answer is 3.

Difficulty: interview

Starter code:

Solutions:
# cook your dish here
# cook your dish here
t=int(input())
for _ in range(t):
 n,p,q=list(map(int,input().split(" ")))
 l=list(map(int,input().split(" ")))
 l.sort()
 s=sum(l)
 a=p+2*q
 b=0
 for i in l:
  if(p==0):
   if(i%2==0 and a>=i):
    a=a-i
    b=b+1
  elif(q==0):
   if(a>=i):
    a=a-i
    b=b+1
  else:
   if(i%2==0 and a>=i):
    a=a-i
    b=b+1
   elif(i%2!=0 and p!=0 and a>=i):
    a=a-i
    b=b+1
    p=p-1

 print(b) 
    
   


# cook your dish here
t=int(input())
for _ in range(t):
 n,p,q=list(map(int,input().split(" ")))
 l=list(map(int,input().split(" ")))
 l.sort()
 s=sum(l)
 a=p+2*q
 b=0
 for i in l:
  if(p==0):
   if(i%2==0 and a>=i):
    a=a-i
    b=b+1
  elif(q==0):
   if(a>=i):
    a=a-i
    b=b+1
  else:
   if(i%2==0 and a>=i):
    a=a-i
    b=b+1
   elif(i%2!=0 and p!=0 and a>=i):
    a=a-i
    b=b+1
    p=p-1

 print(b) 
    
   


# cook your dish here
for _ in range(int(input())):
 
 n,p,q=list(map(int,input().split()))
 
 l=sorted(map(int,input().split()))
 ans=0
 if q==0:
  
  ans=0
  for amount in l:
   
   if amount<=p:
    p-=amount
    ans+=1
   if p==0:
    break
   
  print(ans)
  
 elif p==0:
  ans=0
  for amount in l:
   
   if amount%2==0:
    
    k=amount//2
    
    if k<=q:
     q-=k
     ans+=1
     
   if q==0:
    break
  
  print(ans)
  
  
 else:
  ans=0
  
  for amount in l:
   k=amount//2
   if k<=q:
    amount-=(k*2)
    q-=k
   else:
    amount-=(q*2)
    q-=q
    
   if amount<=p:
    p-=amount
    amount-=amount
    
   else:
    amount-=p
    p-=p
   if amount==0:
    ans+=1
  
   if p==0 and q==0:
    break
    
  print(ans)
     
  
  
  
  
  
  


# cook your dish here
for _ in range(int(input())):
 
 n,p,q=list(map(int,input().split()))
 
 l=sorted(map(int,input().split()))
 ans=0
 if q==0:
  
  ans=0
  for amount in l:
   
   if amount<=p:
    p-=amount
    ans+=1
   if p==0:
    break
   
  print(ans)
  
 elif p==0:
  ans=0
  for amount in l:
   
   if amount%2==0:
    
    k=amount//2
    
    if k<=q:
     q-=k
     ans+=1
     
   if q==0:
    break
  
  print(ans)
  
  
 else:
  ans=0
  
  for amount in l:
   k=amount//2
   if k<=q:
    amount-=k*2
    q-=k
   else:
    amount-=q*2
    q-=q
    
   if amount<=p:
    p-=amount
    amount-=amount
    
   else:
    amount-=p
    p-=p
   if amount==0:
     ans+=1
  
   if p==0 and q==0:
    break
    
  print(ans)
     
  
  
  
  
  
  


# cook your dish here
for _ in range(int(input())):
 
 n,p,q=list(map(int,input().split()))
 
 l=sorted(map(int,input().split()))
 ans=0
 if q==0:
  
  ans=0
  for amount in l:
   
   if amount<=p:
    p-=amount
    ans+=1
   if p==0:
    break
   
  print(ans)
  
 elif p==0:
  ans=0
  for amount in l:
   
   if amount%2==0:
    
    k=amount//2
    
    if k<=q:
     q-=k
     ans+=1
     
   if q==0:
    break
  
  print(ans)
  
  
 else:
  ans=0
  
  for amount in l:
   check=0
   while amount>0:
    
    if q>0 and amount>=2:
     amount-=2
     q-=1
    elif p>0:
     amount-=1
     p-=1
    if p==0 and q==0:
     break
    
   if amount==0:
    ans+=1
   
   if p==0 and q==0:
    break
   
  print(ans)
     
  
  
  
  
  
  


# cook your dish here
for _ in range(int(input())):
 
 n,p,q=list(map(int,input().split()))
 
 l=sorted(map(int,input().split()))
 ans=0
 for amount in l:
  check=0
  while amount>0:
   
   if q>0 and amount>=2:
    amount-=2
    q-=1
   elif p>0:
    amount-=1
    p-=1
   if p==0 and q==0:
    break
   
  if amount==0:
   ans+=1
  
  if p==0 and q==0:
   break
  
 print(ans)


# cook your dish here
for _ in range(int(input())):
 
 n,p,q=list(map(int,input().split()))
 
 l=sorted(map(int,input().split()))
 ans=0
 for amount in l:
  check=0
  while amount>0:
   
   if q>0 and amount>=2:
    amount-=2
    q-=1
   elif p>0:
    amount-=1
    p-=1
   if p==0 and q==0:
    break
   
  if amount==0:
   ans+=1
  
  if p==0 and q==0:
   break
  
 print(ans)


t=int(input())
for _ in range(t):
 n,p,q=map(int,input().split())
 a=list(map(int,input().split()))
 a.sort()
 count=0
 for i in a:
  if(p==0 and q==0):
   break
  elif(i%2==0):
   if(q>=i//2):
    count+=1
    q-=i//2
   else:
    if(p>=i-q-q):
     count+=1
     p-=i-q-q
     q=0
    else:
     continue
  else:
   if(q>=i//2 ):
    if(p>0):
     count+=1
     p-=1
     q-=i//2
    else:
     continue
   else:
    if(p>=max(i-q-q,-1)):
     count+=1
     p-=i-q-q
     q=0
     #print("hii")
    else:
     continue
 print(count)

try:
 for _ in range(int(input())):
  n,p,q=list(map(int,input().split()))
  l=list(map(int,input().split()))
  l.sort()
  for i in range(n):
   if(l[i]%2==0):
    a=l[i]//2
    q=q-a
    if(q>=0):
     l[i]=l[i]-(2*a)
    else:
     break
  i=0
  while(p>=0 and i<n):
   p=p-l[i]
   if(p>=0):
    l[i]=0
   i+=1
  print(l.count(0))
   
   
   
  
except:
 pass


# cook your dish here
try:
 for _ in range(int(input())):
  n,p,q=list(map(int,input().split()))
  l=list(map(int,input().split()))
  l.sort()
  for i in range(n):
   a=l[i]//2
   q=q-a
   if(q>=0):
    l[i]=l[i]-(2*a)
   else:
    break
  i=0
  while(p>=0 and i<n):
   p=p-l[i]
   if(p>=0):
    l[i]=0
   i+=1
  print(l.count(0))
   
   
   
  
except:
 pass


# cook your dish here
t=int(input())
while t>0:
 n,p,q=input().split(" ")
 n=int(n)
 p=int(p)
 q=int(q)
 l=list(map(int,input().split(" ")))
 if q==0:
  s=0
  count=0
  l.sort()
  for i in l:
   s=s+i
   if s>p:
    break
   else:
    count=count+1
  print(count)
 elif p==0:
  l1=list(filter(lambda x:x%2==0,l))
  s=0
  count=0
  l1.sort()
  for i in l1:
   s=s+i
   if s>2*q:
    break
   else:
    count=count+1
  print(count)
 else:
  count=0
  s=0
  sum=p+2*q
  l1=list(filter(lambda x:x%2,l))
  l2=list(filter(lambda x:x%2==0,l))
  l1.sort()
  l2.sort()
  if len(l1)<=len(l2):
   x=len(l1)
  else:
   x=len(l2)
  i=0
  j=0
  lst=[]
  while i+j<len(l1)+len(l2):
   if i==len(l1):
    lst.append(l2[j])
    j=j+1
   elif j==len(l2):
    lst.append(l1[i])
    i=i+1
   elif l1[i]<l2[j]:
    if p>0:
     lst.append(l1[i])
     p=p-1
     i=i+1
    else:
     i=i+1
   else:
    lst.append(l2[j])
    j=j+1
  for i in lst:
   s=s+i
   if s>sum:
    break
   else:
    count=count+1
  print(count)
     
    
 t=t-1

# cook your dish here
t=int(input())
while t>0:
 n,p,q=input().split(" ")
 n=int(n)
 p=int(p)
 q=int(q)
 l=list(map(int,input().split(" ")))
 if q==0:
  s=0
  count=0
  l.sort()
  for i in l:
   s=s+i
   if s>p:
    break
   else:
    count=count+1
  print(count)
 elif p==0:
  l1=list(filter(lambda x:x%2==0,l))
  s=0
  count=0
  l1.sort()
  for i in l1:
   s=s+i
   if s>2*q:
    break
   else:
    count=count+1
  print(count)
 else:
  count=0
  s=0
  sum=p+2*q
  l1=list(filter(lambda x:x%2,l))
  l2=list(filter(lambda x:x%2==0,l))
  l1.sort()
  l2.sort()
  if len(l1)<=len(l2):
   x=len(l1)
  else:
   x=len(l2)
  i=0
  j=0
  lst=[]
  while i+j<len(l1)+len(l2)-1:
   if i==len(l1):
    lst.append(l2[j])
    j=j+1
   if j==len(l2):
    lst.append(l1[i])
    i=i+1
   if l1[i]<l2[j]:
    if p>0:
     lst.append(l1[i])
     p=p-1
     i=i+1
    else:
     i=i+1
   else:
    lst.append(l2[j])
    j=j+1
  for i in lst:
   s=s+i
   if s>sum:
    break
   else:
    count=count+1
  print(count)
     
    
 t=t-1

# cook your dish here
t=int(input())
while t>0:
 n,p,q=input().split(" ")
 n=int(n)
 p=int(p)
 q=int(q)
 l=list(map(int,input().split(" ")))
 if q==0:
  s=0
  count=0
  l.sort()
  for i in l:
   s=s+i
   if s>p:
    break
   else:
    count=count+1
  print(count)
 elif p==0:
  l1=list(filter(lambda x:x%2==0,l))
  s=0
  count=0
  l1.sort()
  for i in l1:
   s=s+i
   if s>2*q:
    break
   else:
    count=count+1
  print(count)
 else:
  sum=p+2*q
  s=0
  count=0
  for i in l:
   s=s+i
   if s>sum:
    break
   else:
    count=count+1
  print(count)
   
  
 t=t-1

# cook your dish here
t=int(input())
while t>0:
 n,p,q=input().split(" ")
 n=int(n)
 p=int(p)
 q=int(q)
 l=list(map(int,input().split(" ")))
 if q==0:
  s=0
  count=0
  l.sort()
  for i in l:
   s=s+i
   if s>p:
    break
   else:
    count=count+1
  print(count)
 elif p==0:
  l1=list(filter(lambda x:x%2==0,l))
  s=0
  count=0
  l1.sort()
  for i in l1:
   s=s+i
   if s>2*q:
    break
   else:
    count=count+1
  print(count)
   
  
 t=t-1

# cook your dish here
t=int(input())
while t>0:
 n,p,q=input().split(" ")
 n=int(n)
 p=int(p)
 q=int(q)
 l=list(map(int,input().split(" ")))
 if q==0:
  s=0
  count=0
  l.sort()
  for i in l:
   s=s+i
   if s>p:
    break
   else:
    count=count+1
  print(count)
   
  
 t=t-1

# cook your dish here
t=int(input())
for _ in range(t):
 n,p,q=map(int,input().split())
 a=list(map(int,input().split()))
 a.sort()
 count=0
 for i in a:
  if(p==0 and q==0):
   break
  elif(i%2==0):
   if(q>=i//2):
    count+=1
    q-=i//2
   else:
    if(p>=i-q-q):
     count+=1
     p-=i-q-q
     q=0
    else:
     continue
  else:
   if(q>=i//2 ):
    if(p>0):
     count+=1
     p-=1
     q-=i//2
    else:
     continue
   else:
    if(p>=max(i-q-q,-1)):
     count+=1
     p-=i-q-q
     q=0
     #print("hii")
    else:
     continue
 print(count)

# cook your dish here
t=int(input())
for _ in range(t):
 n,p,q=map(int,input().split())
 a=list(map(int,input().split()))
 a.sort()
 count=0
 for i in a:
  if(p==0 and q==0):
   break
  elif(i%2==0):
   if(q>=i//2):
    count+=1
    q-=i//2
   else:
    if(p>=i-q-q):
     count+=1
     p-=i-q-q
     q=0
    else:
     continue
  else:
   if(q>=i//2 ):
    if(p>0):
     count+=1
     p-=1
     q-=i//2
    else:
     continue
   else:
    if(p>max(i-q-q,0)):
     count+=1
     p-=i-q-q
     q=0
     #print("hii")
    else:
     continue
 print(count)

# cook your dish here
t=int(input())
for _ in range(t):
 n,p,q=map(int,input().split())
 a=list(map(int,input().split()))
 a.sort()
 count=0
 for i in a:
  if(p==0 and q==0):
   break
  elif(i%2==0):
   if(q>=i//2):
    count+=1
    q-=i//2
   else:
    if(p>=i-q-q):
     count+=1
     p-=i-q-q
     q=0
    else:
     continue
  else:
   if(q>=i//2 ):
    if(p>0):
     count+=1
     p-=1
     q-=i//2
    else:
     continue
   else:
    if(p>max(i-q-q,0)):
     count+=1
     p-=i-q-q
     q=0
     #print("hii")
    else:
     continue
 print(count)

# cook your dish here
t=int(input())
for _ in range(t):
 n,p,q=map(int,input().split())
 a=list(map(int,input().split()))
 a.sort()
 count=0
 for i in a:
  if(p==0 and q==0):
   break
  elif(i%2==0):
   if(q>=i//2):
    count+=1
    q-=i//2
   else:
    if(p>=i-q-q):
     count+=1
     p-=i-q-q
     q=0
    else:
     continue
  else:
   if(q>=i//2 and p>0):
    count+=1
    p-=1
    q-=i//2
   else:
    if(p>max(i-q-q,0)):
     count+=1
     p-=i-q-q
     q=0
     #print("hii")
    else:
     continue
 print(count)

# cook your dish here
t=int(input())
for _ in range(t):
 n,p,q=map(int,input().split())
 a=list(map(int,input().split()))
 a.sort()
 count=0
 for i in a:
  if(p==0 and q==0):
   break
  elif(i%2==0):
   if(q>=i//2):
    count+=1
    q-=i//2
   else:
    if(p>=i-q-q):
     count+=1
     p-=i-q-q
     q=0
    else:
     continue
  else:
   if(q>=i//2 and p>0):
    count+=1
    p-=1
    q-=i//2
   else:
    if(p>=i-q-q):
     count+=1
     p-=i-q-q
     q=0
    else:
     continue
 print(count)

# cook your dish here
t=int(input())
for _ in range(t):
 n,p,q=map(int,input().split())
 a=list(map(int,input().split()))
 a.sort()
 count=0
 for i in a:
  if(i%2==0):
   if(q>=i//2):
    count+=1
    q-=i//2
   else:
    if(p>=i-q-q):
     count+=1
     p-=i-q-q
     q=0
    else:
     break
  else:
   if(q>=i//2 and p>0):
    count+=1
    p-=1
    q-=i//2
   else:
    if(p>=i-q-q):
     count+=1
     p-=i-q-q
     q=0
    else:
     break
 print(count)

for _ in range(int(input())):
 n,p,q=map(int,input().split())
 l=list(map(int,input().split()))
 l.sort()
 ans=0
 for i in range(n):
  x=min(q,l[i]//2)
  l[i]-=x*2
  if(l[i]<=p):
   p-=l[i]
   q-=x
   ans+=1
 print(ans)

for _ in range(int(input())):
 n,p,q=map(int,input().split())
 l=list(map(int,input().split()))
 l.sort()
 ans=0
 for i in range(n):
  x=min(q,l[i]//2)
  l[i]-=x*2
  if(l[i]<=p):
   p-=l[i]
   q-=x*2
   ans+=1
 print(ans)

for _ in range(int(input())):
 n,p,q=map(int,input().split())
 l=list(map(int,input().split()))
 l.sort()
 ans=0
 for i in range(n):
  x=l[i]//2
  if(q>0):
   if(q>=x and q>0):
    q-=x
    l[i]-=x*2
   else:
    l[i]-=q*2
    q=0
    x=0
  p-=l[i]
  if(p<0 and q<=0):
   break
  ans+=1
 print(ans)