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

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(min(n * m, l + r + z + b))
	else:
		temp = l + r + (hand_rest - l - r) / 2
		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)
		elif 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
			elif 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 n <= p:
		print(min(n * m, z + r + b))
	else:
		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)))


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(seat_max)
	else:
		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)
			elif 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


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
			elif 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)