Read problems statements in Mandarin Chinese, Russian and Vietnamese as well. 

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

$1 ≤ T ≤ 10^{5} 
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 ≤ 10^{9} 

Subtask 3 : 30 points
1 ≤ N, M ≤ 10^{6} 
0 ≤ Z, L, R ≤ 10^{6} 
0 ≤ B ≤ 10^{16} 

Subtask 4 : 40 points 
1 ≤ N, M ≤ 10^{8} 
0 ≤ Z, L, R, B ≤ 10^{16} 

------ 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: VERY_HARD
Tags: Sorting

Greedy algorithms

Complete search

Mathematics

Matrices
Skill types: Complete search

Sorting

Greedy algorithms

Starter code:

Solutions:
for i in range(0, int(input())):
	(N, M, Z, L, R, B) = list(map(int, input().split()))
	print(min(N * M, Z + L + R + min(B, N * (M + 1) - L - R >> 1, N * (M + 1 >> 1))))


def seating_arrangement(T):
	max_people = []
	for i in range(T):
		(N, M, Z, L, R, B) = map(int, input().strip().split())
		max_people.append(min(N * M, L + R + Z + min(B, N * (M + 1) - L - R >> 1, N * (M + 1 >> 1))))
	return max_people
T = int(input())
for i in seating_arrangement(T):
	print(i)


tc = int(input())
for t in range(tc):
	(n, m, z, l, r, b) = map(int, input().strip().split())
	print(min(n * m, l + r + z + min(b, n * (m + 1) - l - r >> 1, n * (m + 1 >> 1))))


import math
cases = []
for i in range(int(input())):
	cases.append(input().split())
for case in cases:
	N = int(case[0])
	M = int(case[1])
	Z = int(case[2])
	L = int(case[3])
	R = int(case[4])
	B = int(case[5])
	if L + R + Z >= M * N:
		print(M * N)
	else:
		arr1 = math.floor((N * (M + 1) - L - R) / 2)
		arr2 = math.ceil(M / 2) * N
		arr3 = M * N - L - R - Z
		print(Z + L + R + min(B, arr1, arr2, arr3))


cas = int(input())
for iii in range(cas):
	(n, m, z, l, r, b) = [int(x) for x in input().split()]
	tot = z + l + r + b
	ans = 0
	if b <= n:
		print(min(m * n, tot))
	elif z >= b:
		print(min(m * n, tot))
	elif m == 1:
		print(min(m * n, tot))
	elif m % 2 == 1:
		fillrl = int((l + r) / (m - 1))
		if fillrl >= n:
			one = l + r
			one -= fillrl * (m - 1)
			if one + z + b >= n:
				print(m * n)
			else:
				print(tot)
			continue
		left = l + r - (m - 1) * fillrl + 1
		lefts = m - left
		ans = fillrl * m + left
		b -= fillrl + 1
		if lefts % 2 == 0:
			if z >= lefts >> 1 and b >= lefts >> 1:
				ans = ans + lefts
				z -= int(round(lefts >> 1))
				b -= int(round(lefts >> 1))
			elif b < lefts >> 1 and b + z >= lefts:
				ans = ans + lefts
				z -= lefts - b
				b = 0
			elif b >= lefts >> 1 and z < lefts >> 1:
				ans = int(round(ans + (lefts >> 1) + z))
				z = 0
				b -= int(round(lefts >> 1))
			else:
				ans = ans + b + z
				b = 0
				z = 0
				print(int(round(ans)))
				continue
		else:
			lefts -= 1
			if z >= (lefts >> 1) + 1 and b >= lefts >> 1:
				ans = ans + lefts + 1
				z -= int(round((lefts >> 1) + 1))
				b -= int(round(lefts >> 1))
			elif b < lefts >> 1 and b + z >= lefts + 1:
				ans = ans + lefts + 1
				z -= lefts + 1 - b
				b = 0
			elif b >= lefts >> 1 and z < (lefts >> 1) + 1:
				ans = ans + int(round(lefts >> 1)) + z
				z = 0
				b -= int(round(lefts >> 1))
			else:
				ans = ans + b + z
				b = 0
				z = 0
				print(int(round(ans)))
				continue
		fillrl += 1
		leftrl = n - fillrl
		if b >= leftrl * (m - 1 >> 1) + leftrl:
			ans = ans + int(leftrl * (m - 1 >> 1)) + leftrl
			if z >= leftrl * (m - 1 >> 1):
				ans = int(round(ans + leftrl * (m - 1 >> 1)))
			else:
				ans = ans + z
		else:
			ans = ans + b
			if b + z >= leftrl * m:
				ans = int(round(ans - b + leftrl * m))
			else:
				ans = ans + z
		print(int(round(ans)))
	else:
		one = l + r
		if one <= n:
			ans = one
			one = 0
			left = n - ans
			if z >= left:
				z -= left
				ans += left
			else:
				ans += z
				z = 0
			if b >= m * n >> 1:
				ans += int(round(m * n >> 1))
				if z >= ((m >> 1) - 1) * n:
					ans += int(round(((m >> 1) - 1) * n))
				else:
					ans += z
			elif b + z > (m - 1) * n:
				ans += (m - 1) * n
			else:
				ans += b + z
			print(ans)
			continue
		if m == 2:
			if b >= n:
				ans = n
				if one + z >= n:
					ans += n
				else:
					ans += one + z
			else:
				ans = min(tot, 2 * n)
			print(ans)
			continue
		ans = n
		one -= n
		m -= 1
		fillrl = int(one / (m - 1))
		if fillrl >= n:
			one -= fillrl * (m - 1)
			if one + z + b >= n:
				print((m + 1) * n)
			else:
				print(tot)
			continue
		left = one - (m - 1) * fillrl + 1
		lefts = m - left
		ans += fillrl * m + left
		b -= fillrl + 1
		if lefts % 2 == 0:
			if z >= lefts >> 1 and b >= lefts >> 1:
				ans = ans + lefts
				z -= int(round(lefts >> 1))
				b -= int(round(lefts >> 1))
			elif b < lefts >> 1 and b + z >= lefts:
				ans = ans + lefts
				z -= lefts - b
				b = 0
			elif b >= lefts >> 1 and z < lefts >> 1:
				ans = int(round(ans + (lefts >> 1) + z))
				z = 0
				b -= int(round(lefts >> 1))
			else:
				ans = ans + b + z
				b = 0
				z = 0
				print(int(round(ans)))
				continue
		else:
			lefts -= 1
			if z >= (lefts >> 1) + 1 and b >= lefts >> 1:
				ans = ans + lefts + 1
				z -= int(round((lefts >> 1) + 1))
				b -= int(round(lefts >> 1))
			elif b < lefts >> 1 and b + z >= lefts + 1:
				ans = ans + lefts + 1
				z -= lefts + 1 - b
				b = 0
			elif b >= lefts >> 1 and z < (lefts >> 1) + 1:
				ans = ans + int(round(lefts >> 1)) + z
				z = 0
				b -= int(round(lefts >> 1))
			else:
				ans = ans + b + z
				b = 0
				z = 0
				print(int(round(ans)))
				continue
		fillrl += 1
		leftrl = n - fillrl
		if b >= leftrl * (m - 1 >> 1) + leftrl:
			ans = ans + int(leftrl * (m - 1 >> 1)) + leftrl
			if z >= leftrl * (m - 1 >> 1):
				ans = int(round(ans + leftrl * (m - 1 >> 1)))
			else:
				ans = ans + z
		else:
			ans = ans + b
			if b + z >= leftrl * m:
				ans = int(round(ans - b + leftrl * m))
			else:
				ans = ans + z
		print(int(round(ans)))


from sys import stdin
_data = iter(stdin.read().split('\n'))
input = lambda : next(_data)

def solve_med(n, m, z, l, r, b):
	memo = {}

	def dfs(i, j, z, l, r, b, prev):
		s = (i, j, z, l, r, b, prev)
		if s in memo:
			return memo[s]
		if j == m:
			if i == n - 1:
				return 0
			else:
				memo[s] = dfs(i + 1, 0, z, l, r, b, False)
				return memo[s]
		ans = 0
		if z > 0:
			ans = max(ans, dfs(i, j + 1, z - 1, l, r, b, False) + 1)
		else:
			ans = max(ans, dfs(i, j + 1, 0, l, r, b, False))
		if l > 0 and (not prev):
			ans = max(ans, dfs(i, j + 1, z, l - 1, r, b, False) + 1)
		if r > 0:
			ans = max(ans, dfs(i, j + 1, z, l, r - 1, b, True) + 1)
		if b > 0 and (not prev):
			ans = max(ans, dfs(i, j + 1, z, l, r, b - 1, True) + 1)
		memo[s] = ans
		return ans
	return dfs(0, 0, z, l, r, b, False)

def solve(n, m, z, l, r, b):
	if m == 1:
		return min(n, z + l + r + b)
	(p, q) = (0, 0)
	ans = 0
	lr = l + r
	lrb_line = min(b, n, lr // (m - 1))
	n -= lrb_line
	b -= lrb_line
	lr -= lrb_line * (m - 1)
	ans += m * lrb_line
	p += (m - 1) // 2 * lrb_line
	if n == 0:
		return ans
	if b == 0:
		ans += min(n * m, lr + z)
		return ans
	rest = 0
	non = 0
	if lr > 0:
		ans += lr
		rest = m - lr
		n -= 1
		bct = min(b, (rest + 1) // 2)
		non += rest - bct
		ans += bct
		b -= bct
		if b > 0 and rest % 2 == 0 and (m % 2 == 0):
			p += (lr - 1) // 2
			lr = 1
			b -= 1
		else:
			p += lr // 2
			lr = 0
	q = n if m % 2 == 0 and m >= 4 else 0
	bct = min(b, (m + 1) // 2 * n)
	non += n * m - bct
	ans += bct
	b -= bct
	lr2 = l + r
	if q > 0 and lr > 0:
		lr = 0
		q -= 1
		non -= 1
		ans += 1
	if q > 0:
		bct = min(b, q // 2, p)
		non -= bct
		ans += bct
	return ans + min(z, non)
for _ in range(int(input())):
	(n, m, z, l, r, b) = map(int, input().split())
	ans = solve(n, m, z, l, r, b)
	print(ans)