Probably everyone has experienced an awkward situation due to shared armrests between seats in cinemas. A highly accomplished cinema manager named "Chef" decided to solve this problem.

When a customer wants to buy a ticket, the clerk at the ticket window asks the visitor if they need the armrests, and if so, which of them: left, right, or both. We know that out of the audience expected to show up, L of them only need the left armrest, R of them need just the right one, Z need none and B need both. Your task is to calculate the maximum number of people that can attend the show. In the cinema hall there are N rows with M seats each. There is only one armrest between two adjacent seats. Seats at the beginning and at the end of the row have two armrests

-----Input-----

Input begins with an integer T: the number of test cases.

Each test case consists of a single line with 6 space-separated integers: N, M, Z, L, R, B.

-----Output-----

For each test case, output a line containing the answer for the task.

-----Constraints and Subtasks-----
- 1 ≤ T ≤ 105 
Subtask 1 : 10 points 
- 1 ≤ N, M ≤ 3 
- 0 ≤ Z, L, R, B ≤ 3 
Subtask 2 : 20 points 
- 1 ≤ N, M ≤ 30 
- 0 ≤ Z, L, R ≤ 30 
- 0 ≤ B ≤ 109 
Subtask 3 : 30 points
- 1 ≤ N, M ≤ 106 
- 0 ≤ Z, L, R ≤ 106 
- 0 ≤ B ≤ 1016 
Subtask 4 : 40 points
- 1 ≤ N, M ≤ 108 
- 0 ≤ Z, L, R, B ≤ 1016 

-----Example-----
Input:2
2 2 3 2 1 1
3 3 1 2 0 9

Output:4
8

-----Explanation-----
'L' - needs left

'R - needs right

'Z' - doesn't need any

'B' - needs both

'-' - empty place

Example case 1.
ZZ

ZB
Example case 2.
LLB

BZB

B-B

Difficulty: interview

Starter code:

Solutions:
for i in range(eval(input())):
 n,m,z,l,r,b = list(map(int, input().split()))
 rows=n
 columns=m
 hand_rest=n*(m+1)
 if(m%2==0):
  hand_rest -=max(0,n-l-r)
 if(l+r+(2*b)<=hand_rest):
  # print "kanu"
  print(min(n*m,l+r+z+b))
 else:
  temp=l+r+(hand_rest-l-r)/2
  # print "parth"
  print(min(n*m,temp+z))

t=int(input())
while(t):
 t-=1
 n,m,z,l,r,b=list(map(int,input().split()))
 if(m!=1):
  if(b>=n):
   ba=n
   bl=b-n
  else:
   ba=b
   b1=0
  if(ba==n):
   if((l+r)>=n*(m-1)):
    ans=n*m
   else:
    w=(l+r)%(m-1)
    la=l
    ll=0
    ra=r
    rl=0
    x=(m-1)/2
    y=n-(l+r)/(m-1)
    if(w==0):
     if(bl>=(x*y)):
      ba+=x*y
      bl=b-ba
     else:
      ba=b
      bl=0
    else:
     y-=1
     u=m-1-w
     if(bl>=(u/2+x*y)):
      ba+=(u/2+x*y)
      bl=b-ba
     else:
      ba=b
      bl=0
    za=min(n*m-la-ra-ba,z)
    zl=z-za
    ans=min(n*m,la+ra+ba+za)
  else:
   if((l+r)>=n*m-b):
    ans=n*m
   else:
    la=l
    ll=0
    ra=r
    rl=0
    za=min(n*m-la-ra-ba,z)
    zl=z-za
    ans=min(n*m,la+ra+ba+za)
 else:
  ans=min(n*m,l+r+z+b)
 print(ans)
      


t=eval(input())
while t>0:
 xx=list(map(int,input().split()))
 n=xx[0]
 m=xx[1]
 z=xx[2]
 l=xx[3]
 r=xx[4]
 b=xx[5]
 total=z+l+r+b
 maxi=n*m
 count=0
 ar = [[0 for y in range(m)] for x in range(n)]
 truth=True
 i=0
 while i<n:
  j=0
  while j<m:
   ar[i][j]=0
   if j==0:
    if l!=0:
     l=l-1
     ar[i][0]=-1
     count=count+1
     if count==total:
      truth=False
      break
    elif b!=0:
     b=b-1
     ar[i][0]=2
     count=count+1
     if count==total:
      truth=False
      break
    elif r!=0:
     r=r-1
     ar[i][0]=1
     count=count+1
     if count==total:
      truth=False
      break
    elif z!=0:
     z=z-1
     ar[i][0]=0
     count=count+1
     if count==total:
      truth=False
      break
   elif j==(m-1):
    if ar[i][j-1]==-1:
     if b!=0:
      b=b-1
      ar[i][j]=2
      count=count+1
      if count==total:
       truth=False
       break
     elif r!=0:
      r=r-1
      ar[i][j]=1
      count=count+1
      if count==total:
       truth=False
       break
     elif l!=0:
      l=l-1
      ar[i][j]=-1
      count=count+1
      if count==total:
       truth=False
       break
     elif z!=0:
      z=z-1
      ar[i][j]=0
      count=count+1
      if count==total:
       truth=False
       break
    elif ar[i][j-1]==2:
     if r!=0:
      r=r-1
      ar[i][j]=1
      count=count+1
      if count==total:
       truth=False
       break
     elif z!=0:
      z=z-1
      ar[i][j]=0
      count=count+1
      if count==total:
       truth=False
       break
    elif ar[i][j-1]==1:
     if r!=0:
      r=r-1
      ar[i][j]=1
      count=count+1
      if count==total:
       truth=False
       break
     elif z!=0:
      z=z-1
      ar[i][j]=0
      count=count+1
      if count==total:
       truth=False
       break
    elif ar[i][j-1]==0:
     if b!=0:
      b=b-1
      ar[i][j]=2
      count=count+1
      if count==total:
       truth=False
       break
     elif r!=0:
      r=r-1
      ar[i][j]=1
      count=count+1
      if count==total:
       truth=False
       break
     elif l!=0:
      l=l-1
      ar[i][j]=-1
      count=count+1
      if count==total:
       truth=False
       break
     elif z!=0:
      z=z-1
      ar[i][j]=0
      count=count+1
      if count==total:
       truth=False
       break
   else:
    if ar[i][j-1]==-1:
     if l!=0:
      l=l-1
      ar[i][j]=-1
      count=count+1
      if count==total:
       truth=False
       break
     elif b!=0:
      b=b-1
      ar[i][j]=2
      count=count+1
      if count==total:
       truth=False
       break
     elif r!=0:
      r=r-1
      ar[i][j]=1
      count=count+1
      if count==total:
       truth=False
       break
     elif z!=0:
      z=z-1
      ar[i][j]=0
      count=count+1
      if count==total:
       truth=False
       break
    elif ar[i][j-1]==2:
     if r!=0:
      r=r-1
      ar[i][j]=1
      count=count+1
      if count==total:
       truth=False
       break
     elif z!=0:
      z=z-1
      ar[i][j]=0
      count=count+1
      if count==total:
       truth=False
       break
    elif ar[i][j-1]==1:
     if r!=0:
      r=r-1
      ar[i][j]=1
      count=count+1
      if count==total:
       truth=False
       break
     elif z!=0:
      z=z-1
      ar[i][j]=0
      count=count+1
      if count==total:
       truth=False
       break
    elif ar[i][j-1]==0:
     if l!=0:
      l=l-1
      ar[i][j]=-1
      count=count+1
      if count==total:
       truth=False
       break
     elif b!=0:
      b=b-1
      ar[i][j]=2
      count=count+1
      if count==total:
       truth=False
       break
     elif r!=0:
      r=r-1
      ar[i][j]=1
      count=count+1
      if count==total:
       truth=False
       break
     elif z!=0:
      z=z-1
      ar[i][j]=0
      count=count+1
      if count==total:
       truth=False
       break
   
   if truth==False:
    break
   j=j+1
  if truth==False:
   break
  i=i+1
 print(count)
 t=t-1
     


for _ in range(int(input())):
 n,m,z,l,r,b = list(map(int,input().split())) 
 r = r + l
 c = 0
 if m == 1:
  print(min(n*m,z+r+b))
  continue
 elif m%2 == 0:
  m -= 1 
  if n >= r:
   c += r
   R = n-r
   r = 0
   if z <= R:
    c += z
    z = 0
   else:
    c += R
    z -= R 
  else:
   c += n
   r -= n 
 b += (r%2) 
 r -= (r%2)
 if m == 1:
  print(min(n*m,z+r+b) + c)
  continue
 p = r/(m-1)
 k = min(b-p,(m+1-(r-p*(m-1)))/2 + (n-p-1)*((m+1)/2)) + p 
 print(min(n*m,z+r+k) + c)
  
  


for _ in range(int(input())):
 n,m,z,l,r,b = list(map(int,input().split())) 
 r = r + l
 if (m == 1):
  print(min(n*m,z+r+b))
  continue
 p = r/(m-1) 
 if (m % 2 == 0):
  k = min(b-p,(m-max(0,(r-p*(m-1)-(n-p))))/2 + ((n-p-1)*(m/2))) + p 
  print(min(n*m,z+r+k))
 else:
  k = min(b-p,(m+1-(r-p*(m-1)))/2 + ((n-p-1)*((m+1)/2))) + p 
  print(min(n*m,z+r+k))
  
  


for _ in range(int(input())):
 n,m,z,l,r,b = list(map(int,input().split())) 
 r = r + l
 if (m == 1):
  print(min(n*m,z+r+b))
  continue
 p = r/(m-1) 
 if (m % 2 == 0) and (r-p*(m-1) <= n-p):
  k = min(b-p,(n-p)*(m/2)) + p 
  print(min(n*m,z+r+k))
 else:
  k = min(b-p,(m+1-(r-p*(m-1)))/2 + ((n-p-1)*((m+1)/2))) + p 
  print(min(n*m,z+r+k))

for _ in range(int(input())):
 n,m,z,l,r,b = list(map(int,input().split())) 
 r = r + l
 if (m == 1):
  print(min(n*m,z+r+b))
  continue
 p = r/(m-1)
 if (n <= p): 
  #k = min(b-p,(m+1-(r-p*(m-1)))/2 + ((n-p-1)*((m+1)/2))) + p     
  print(min(n*m,z+r+b))
 else:
  #k = min(b-p,(m+1-min(1,(r-p*(m-1)-(n-p-1))))/2 + ((n-p-1)*((m+1)/2))) +            p     
  #print min(n*m,z+r+k)
  s = min(b-p,(m+1-(r-p*(m-1)))/2 + ((n-p-1)*((m+1)/2))) + p 
  R = r%(m-1)
  h = R%(n-p)
  y = R/(n-p)
  k = min(b-p,((m-y)/2)*h + ((m+1-y)/2)*(n-p-h)) + p
  print(max(min(n*m,z+r+s),min(n*m,z+r+k)))

for _ in range(int(input())):
 n,m,z,l,r,b = list(map(int,input().split())) 
 r = r + l
 if (m == 1):
  print(min(n*m,z+r+b))
  continue
 p = r/(m-1)
 if (n <= p): 
  #k = min(b-p,(m+1-(r-p*(m-1)))/2 + ((n-p-1)*((m+1)/2))) + p     
  print(min(n*m,z+r+b))
 else:
  #k = min(b-p,(m+1-min(1,(r-p*(m-1)-(n-p-1))))/2 + ((n-p-1)*((m+1)/2))) +            p     
  #print min(n*m,z+r+k)
  R = r%(m-1)
  h = R%(n-p)
  y = R/(n-p)
  k = min(b-p,((m-y)/2)*h + ((m+1-y)/2)*(n-p-h)) + p
  print(min(n*m,z+r+k))

for _ in range(int(input())):
 n,m,z,l,r,b = list(map(int,input().split())) 
 r = r + l
 if m == 1:
  print(min(n*m,z+r+b))
  continue
 p = r/(m-1)
 if (m%2 != 0) or (n <= p): 
  k = min(b-p,(m+1-(r-p*(m-1)))/2 + ((n-p-1)*((m+1)/2))) + p 
  print(min(n*m,z+r+k))
 else:
  R = r%(m-1)
  h = R%(n-p)
  y = R/(n-p)
  k = min(b-p,((m-y)/2)*h + ((m+1-y)/2)*(n-p-h)) + p
  print(min(n*m,z+r+k))

for _ in range(int(input())):
 n,m,z,l,r,b = list(map(int,input().split())) 
 r = r + l
 if m == 1:
  print(min(n*m,z+r+b))
 elif m%2: 
  p = r/(m-1)
  k = min(b-p,(m+1-(r-p*(m-1)))/2 + ((n-p-1)*((m+1)/2))) + p 
  print(min(n*m,z+r+k))
 else:
  p = r/(m-1)
  k = min(b-p,(n-p)*(m/2)) + p 
  print(min(n*m,z+r+k))

for _ in range(int(input())):
 n,m,z,l,r,b = list(map(int,input().split())) 
 r = r + l
 if m == 1:
  print(min(n*m,z+r+b))
 elif m%2: 
  p = r/(m-1)
  k = min(b-p,(m+1-(r-p*(m-1)))/2 + ((n-p-1)*((m+1)/2))) + p 
  print(min(n*m,z+r+k))
 else:
  p = r/(m-1)
  k = min(b-p,(n-p)*(m/2)) + p 
  print(min(n*m,z+r+k))

t=eval(input())
for qq in range(t):
 n,m,z,l,r,b=list(map(int,input().split()))
 seat_max=n*m
 seat_used=l+r+z
 armrest_max=n*(m+1)
 armrest_used=l+r
 if (seat_used>=seat_max):
 #   print "used only l,r,z"
  print(seat_max)
 else:
 #   print "armrest_used= ",armrest_used,"seat_used=",seat_used
  armrest_used_by_b=(armrest_max-armrest_used)/2
  seat_used_by_b=min(armrest_used_by_b,b,((m+1)/2)*n)
  seat_used+=seat_used_by_b
  print(min(seat_used,seat_max))


import sys
import math
t=int(eval(input("")))
while t:
 n,m,z,l,r,b=list(map(int,sys.stdin.readline().split()))
 if m==3:
  if n==1:
   if z+l+r+b<3:
    print(z+l+r+b)
   else:
    if b<2 :
     print(3)
    elif b==2 and z<1 and l+r<2:
     print(2)
    elif b==3 and z<1 and l+r<2:
     print(2)
    else:
     print(3)
  elif n==2:
   if z+l+r+b<6:
    print(z+l+r+b)
   elif z!=0:
    print(6)
   elif z==0 and b==3 and z+l+r+b==6:
    print(5)
   else:
    print(6)
  elif n==3:
   if z+l+r+b<9:
    print(z+l+r+b)
   else:
    print(9)
   
    
 elif m==2:
  if n==1:
   if z+l+r+b<2:
    print(z+l+r+b)
   elif l+r+z==0:
    print(1)
   else:
    print(2)
  elif n==2:
   if z+l+r+b<4:
    if z+l+r+b<3:
     print(z+l+r+b)
    elif b==3 and z+l+r==0:
     print(2)
    else:
     print(3)
   elif z+l+r>1:
    print(4)
   else:
    print(3)
  elif n==3:
   if z+l+r+b<6:
    print(z+l+r+b)
   else:
    print(6)
   
 else:
  print(min(m*n,z+l+r+b))
  
 t-=1


def func(n,m,z,l,r,b):
 l=l+r
 if(l>=n*(m-1)):
  return min(n*m,l+z+b)
 x=l/(m-1)
 ans=x*(m-1)
 x=min(b,x)
 ans=ans+x
 b=b-x
 x=l%(m-1)
 ans=ans+x
 x=m-x
 x=min((x/2)+(x%2),b)
 ans=ans+x
 b=b-x
 x=n-(l/(m-1))
 x=x-1
 x=min(b,x*((m/2)+(m%2)))
 ans=ans+x
 z=min(z,n*m-ans)
 ans=ans+z
 return ans
def func2(n,m,z,l,r,b):
 l=l+r
 if(l>=n*(m-1)):
  return min(n*m,l+z+b)
 x=l/(m-1)
 ans=x*(m-1)
 n2=n-x
 x=min(b,x)
 ans=ans+x
 b=b-x
 l=l%(m-1)
 x=l/n2
 ans=ans+x*n2
 m=m-x
 l=l%n2
 ans1=ans+func(n2,m,z,l,0,b)
 ans2=0
 ans3=0
 if(l>0):
  ans2=ans+l
  x=min(z,n2-l)
  ans2=ans2+x
  z=z-x
  m=m-1
  ans2=ans2+func(n2,m,z,0,0,b)
  z=z+x
  m=m+1
  ans3=ans+l
  x=min(b,n2-l)
  ans3=ans3+x
  b=b-x
  m=m-2
  ans3=ans3+func(n2,m,z,0,0,b)
 return max(ans1,ans2,ans3)
t=eval(input())
for _ in range(0,t):
 n,m,z,l,r,b=list(map(int,input().split()))
 a=func(n,m,z,l,r,b)
 a=max(a,func2(n,m,z,l,r,b))
 print(a) 

def mini(a,b):
 if a>=b:
  return b
 else:
  return a

t=eval(input())
while t:
 m,n,z,l,r,b=list(map(int,input().split()))
 x=n*m
 y=m*(n+1)
 A=min(z,x)
 ans=A
 x-=A
 B=min(l,x)
 ans+=B
 x-=B
 C=min(r,x)
 ans+=C
 x-=C
 p=min(b,x)
 x=m*((n+1)//2)
 p=min(p,x)
 x=(y-B-C)//2
 ans+=min(p,x)
 print(ans)
 t-=1

def mini(a,b):
 if a>=b:
  return b
 else:
  return a

t=eval(input())
while t:
 n,m,z,l,r,b=list(map(int,input().split()))
 x=n*m
 y=n*(m+1)
 if (b <= n) or (m == 1):
  print(mini(x,z+l+r+b))
  t-=1
  continue
 if (z+l+r+n) >= x:
  print(x)
  t-=1
  continue
 A=min(z,x)
 x-=A
 B=min(l,x)
 x-=B
 C=min(r,x)
 x-=C
 p=min(b,x)
 p=min(p,m*((n+1)//2))
 p=min(p,(y-B-C)//2)
 print(A+B+C+p)
 t-=1

t=eval(input())
author='biggy_bs'
while t>0:
 t-=1
 n,m,z,l,r,b=list(map(int,input().split()))
 max_b=n*((m+1)/2)
 maximm=n*m
 nm=maximm
 answer=0
 if maximm>l+r:
  author=answer
  answer=l+r
  maximm-=(l+r)
  if m%2!=0:
   if maximm<=n-1:
    if b>=maximm:
     maximm-=maximm
    else:
     maximm-=b
   else:
    if b>=(maximm+n)/2:
     maximm-=(maximm+n)/2
    else:
     maximm-=b 
  else:
   author=n*m
   answer=l+r
   if n*m-maximm<=n:
    if b>=max_b:
     maximm-=max_b
    else:
     maximm-=b
   elif maximm<=n-1:
    if b>=maximm:
     maximm-=maximm
    else:
     maximm-=b
   else:
    answer=b
    if b>=(maximm+n)/2:
     maximm-=(maximm+n)/2
    else:
     maximm-=b
  answer=n*m
  if z>=maximm or maximm==0:
   answer=n*m
  else:
   answer=n*m
   answer=n*m-(maximm-z)
  print(answer)
 else:
  nm=n*m
  answer=nm
  print(answer)


def func(n,m,z,l,r,b):
 l=l+r
 if(l>=n*(m-1)):
  return min(n*m,l+z+b)
 x=l/(m-1)
 ans=x*(m-1)
 x=min(b,x)
 ans=ans+x
 b=b-x
 x=l%(m-1)
 ans=ans+x
 x=m-x
 x=min((x/2)+(x%2),b)
 ans=ans+x
 b=b-x
 x=n-(l/(m-1))
 x=x-1
 x=min(b,x*((m/2)+(m%2)))
 ans=ans+x
 z=min(z,n*m-ans)
 ans=ans+z
 return ans
def func2(n,m,z,l,r,b):
 l=l+r
 if(l>=n*(m-1)):
  return min(n*m,l+z+b)
 x=l/(m-1)
 ans=x*(m-1)
 n2=n-x
 x=min(b,x)
 ans=ans+x
 b=b-x
 l=l%(m-1)
 x=l/n2
 ans=ans+x*n2
 m=m-x
 l=l%n2
 ans1=ans+func(n2,m,z,l,0,b)
 ans2=0
 ans3=0
 if(l>0):
  ans2=ans+l
  x=min(z,n2-l)
  ans2=ans2+x
  z=z-x
  m=m-1
  ans2=ans2+func(n2,m,z,0,0,b)
  z=z+x
  m=m+1
  ans3=ans+l
  x=min(b,n2-l)
  ans3=ans3+x
  b=b-x
  m=m-2
  ans3=ans3+func(n2,m,z,0,0,b)
 return max(ans,ans2,ans3)
t=eval(input())
for _ in range(0,t):
 n,m,z,l,r,b=list(map(int,input().split()))
 a=func(n,m,z,l,r,b)
 a=max(a,func2(n,m,z,l,r,b))
 print(a)