Chef is taking a tough examination. The question paper consists of N objective problems and each problem has 4 options A, B, C, and D, out of which, exactly one option is correct.

Since Chef did not study for the exam, he does not know the answer to any of the problems. Chef was looking nearby for help when his friend somehow communicated the following information:

Exactly N_{A} problems have option A as the answer.
Exactly N_{B} problems have option B as the answer.
Exactly N_{C} problems have option C as the answer.
Exactly N_{D} problems have option D as the answer.

Note that:
N_{A} + N_{B} + N_{C} + N_{D} = N.
Each problem is worth exactly 1 mark and there is no negative marking.
Even though Chef knows the number of correct options of each type, he does not know the correct answer to any problem. 

Based on the given information, find the maximum marks Chef can guarantee if he marks the answers optimally.

------ Input Format ------ 

- First line will contain T, number of test cases. Then the test cases follow.
- First line of each test case contains an integer N denoting the number of problems.
- Second line of each test case contains 4 integers N_{A}, N_{B}, N_{C}, and N_{D} - as mentioned in the problem statement.

------ Output Format ------ 

For each test case, output the maximum marks Chef can guarantee if he marks the answers optimally.

------ Constraints ------ 

$1 ≤ T ≤ 1000$
$1 ≤ N ≤ 10^{5}$
$0 ≤ N_{A}, N_{B}, N_{C}, N_{D} ≤ N$
$N_{A} + N_{B} + N_{C} + N_{D} = N$

----- Sample Input 1 ------ 
2
5
0 0 5 0
10
7 1 1 1

----- Sample Output 1 ------ 
5
7

----- explanation 1 ------ 
Test Case $1$: Chef knows that all the problems have answer as option $C$ and thus he will mark all the answers as $C$ and get $5$ marks.

Test Case $2$: It will be optimal for Chef to mark all the options as $A$ which will yield him $7$ marks. Thus, irrespective of the answer key, Chef can guarantee $7$ marks by marking all answers as option $A$.

Difficulty: EASY
Tags: Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().strip().split()))
	print(max(a))


for _ in range(int(input())):
	n = int(input())
	print(max(map(int, input().split())))


t = int(input())
for i in range(t):
	n = int(input())
	(a, b, c, d) = map(int, input().split())
	print(max(a, b, c, d))


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	print(max(l))


for i in range(int(input())):
	n1 = int(input())
	l = list(map(int, input().split(' ')))
	print(max(l))


t = int(input())
for i in range(t):
	x = int(input())
	y = list(map(int, input().split()))
	print(max(y))


for _ in range(int(input())):
	N = int(input())
	cheat = list(map(int, input().split()))
	if N in cheat:
		print(N)
	else:
		print(max(cheat))


T = int(input())
for i in range(T):
	N = int(input())
	(NA, NB, NC, ND) = map(int, input().split())
	print(max(NA, NB, NC, ND))


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	print(a[3])


for t in range(int(input())):
	n = int(input())
	(na, nb, nc, nd) = map(int, input().split())
	print(max(na, nb, nc, nd))


T = int(input())
for i in range(T):
	N = int(input())
	(A, B, C, D) = map(int, input().split())
	print(max(A, B, C, D))


t = int(input())
for i in range(t):
	N = int(input())
	(Na, Nb, Nc, Nd) = map(int, input().split())
	MaxQues = max(Na, Nb, Nc, Nd)
	print(MaxQues)


t = int(input())
for i in range(t):
	a = int(input())
	N = list(map(int, input().split()))
	print(max(N))


for i in range(int(input())):
	k = int(input())
	a = list(map(int, input().split()))
	e = max(a)
	print(e)


for i in range(int(input())):
	k = int(input())
	(a, b, c, d) = map(int, input().split())
	e = max(a, b, c, d)
	print(e)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split(' ')))
	print(max(a))


for i in range(int(input())):
	n = int(input())
	print(max(map(int, input().split())))


T = int(input())
for tc in range(T):
	e = int(input())
	g = list(map(int, input().split()))
	print(max(g))


T = int(input())
for M in range(T):
	N = int(input())
	n = 4
	num = [int(i) for i in input().split()][:n]
	print(max(num))


t = int(input())
for i in range(t):
	N = int(input())
	c = input()
	v = c.split(' ')
	x = int(v[0])
	y = int(v[1])
	w = int(v[2])
	z = int(v[3])
	if x + y + w + z == N:
		print(max(x, y, z, w))
	else:
		pass


test_cases = int(input())
for i in range(test_cases):
	N = int(input())
	answer = input()
	_answer = answer.split(' ')
	result = []
	sum = 0
	max = 0
	for _ans in _answer[:4]:
		result.append(int(_ans))
		sum = sum + int(_ans)
		if max < int(_ans):
			max = int(_ans)
	print(max)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	maxi = l[0]
	for i in l:
		if i > maxi:
			maxi = i
	print(maxi)


for T in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	max = A[0]
	for i in range(0, len(A)):
		if A[i] > max:
			max = A[i]
	print(max)


n = int(input())
for i in range(n):
	q = int(input())
	ar = list(map(int, input().split(' ')))
	print(max(ar))


test_case = int(input())
for i in range(0, test_case):
	N = int(input())
	print(max(map(int, input().split())))


for i in range(int(input())):
	n = int(input())
	(Na, Nb, Nc, Nd) = map(int, input().split())
	print(max(Na, Nb, Nc, Nd))


T = int(input())
for i in range(0, T):
	n = int(input())
	(a, b, c, d) = map(int, input().split())
	print(max(a, b, c, d))


t = int(input())
while t > 0:
	n = int(input())
	(na, nb, nc, nd) = map(int, input().split())
	print(max(na, nb, nc, nd))
	t -= 1


for i in range(int(input())):
	a = int(input())
	(w, x, y, z) = map(int, input().split())
	print(max(w, x, y, z))


for i in range(int(input())):
	a = int(input())
	lt = list(map(int, input().split()))
	print(max(lt))


n = int(input())
for i in range(0, n):
	a = int(input())
	b = list(map(int, input().split()))
	print(max(b))


t = int(input())
for _ in range(t):
	n = int(input())
	marks = list(map(int, input().split(' ')))
	print(max(marks))


T = int(input())
if T >= 1 and T <= 1000:
	for i in range(0, T):
		N = int(input())
		(N1, N2, N3, N4) = map(int, input().split())
		A = max(N1, N2, N3, N4)
		print(A)


T = int(input())
for _ in range(T):
	K = int(input())
	a = list(map(int, input().strip().split()))
	print(max(a))


for i in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	maxi = 0
	for i in x:
		maxi = max(maxi, i)
	print(maxi)


t = int(input())
for i in range(t):
	n = int(input())
	(a, b, c, d) = list(map(int, input().split()))
	if a >= b and a >= c and (a >= d):
		print(a)
	elif a <= b and b >= c and (b >= d):
		print(b)
	elif a <= c and b <= c and (c >= d):
		print(c)
	elif a <= d and b <= d and (c <= d):
		print(d)


t = int(input())
for i in range(t):
	n = int(input())
	n_list = list(map(int, input().split()))
	n_a = n_list[0]
	n_b = n_list[1]
	n_c = n_list[2]
	n_d = n_list[3]
	print(max(n_list))


for i in range(int(input())):
	x = int(input())
	(a, b, c, d) = map(int, input().split())
	print(max(a, b, c, d))


T = int(input())
for i in range(T):
	N = int(input())
	print(max(map(int, input().split())))


T = int(input())
for i in range(T):
	N = int(input())
	L = list(map(int, input().split()))
	L.sort(reverse=True)
	print(L[0])


t = int(input())
while t > 0:
	t -= 1
	marks = input()
	li = []
	li = map(int, input().split())
	print(max(li))