Read problems statements in Mandarin Chinese, Russian and Vietnamese as well. 
Today a plane was hijacked by a maniac. All the passengers of the flight are taken as hostage. Chef is also one of them.
He invited one of the passengers to play a game with him. If he loses the game, he will release all the passengers, otherwise he will kill all of them. A high risk affair it is.

Chef volunteered for this tough task. He was blindfolded by Hijacker. Hijacker brought a big black bag from his pockets. The contents of the bag is not visible. He tells Chef that the bag contains R red, G green and B blue colored balloons.

Hijacker now asked Chef to take out some balloons from the box such that there are at least K balloons of the same color and hand him over. If the taken out balloons does not contain at least K balloons of the same color, then the hijacker will shoot everybody. Chef is very scared and wants to leave this game as soon as possible, so he will draw the minimum number of balloons so as to save the passengers. Can you please help scared Chef to find out the minimum number of balloons he should take out.

------ Input ------ 

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. 

The first line of each test case contains a three space-separated integers R, G and B. 

The second line contains only one integer K.

------ Output ------ 

For each test case, output a single line containing one integer - the minimum number of balloons Chef need to take out from the bag.

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

$1 ≤ T ≤ 1000$
$1 ≤ R, G, B ≤ 10^{9}$
$1 ≤ K ≤ max{R, G, B}$

------ Subtasks ------ 

$Subtask 1 (44 points): 1 ≤ R, G, B ≤ 10$
$Subtask 2 (56 points):  No additional constraints$

----- Sample Input 1 ------ 
2
3 3 3
1
3 3 3
2
----- Sample Output 1 ------ 
1
4
----- explanation 1 ------ 
Example case 2. In the worst-case scenario first three balloons will be of the three different colors and only after fourth balloon Chef will have two balloons of the same color. So, Chef might need to fetch 4 balloons

Difficulty: EASY
Tags: Mathematics

Starter code:

Solutions:
for _ in range(int(input())):
	l = list(map(int, input().split()))
	n = int(input())
	re = 0
	for i in range(3):
		re += min(l[i], n - 1)
	print(re + 1)


t = int(input())
for i in range(t):
	ins = list(map(int, input().split(' ')))
	k = int(input())
	real = []
	extra = 0
	for i in range(len(ins)):
		if ins[i] >= k:
			real.append(ins[i])
		else:
			extra += ins[i]
	print((k - 1) * len(real) + 1 + extra)


a = int(input())
for i in range(a):
	b = list(map(int, input().split()))
	k = int(input())
	l = len(b)
	e = 0
	for i in b:
		if i >= k - 1:
			e = e + k - 1
		else:
			e = e + i
	print(e + 1)


t = int(input())
for t in range(t):
	arr = [int(i) for i in input().split()]
	k = int(input())
	minm = 0
	for i in range(3):
		minm += min(arr[i], k - 1)
	print(minm + 1)


T = int(input())
for _ in range(T):
	(R, G, B) = map(int, input().split())
	K = int(input())
	result = min(R, K - 1) + min(G, K - 1) + min(B, K - 1) + 1
	print(result)


t = int(input())
for _ in range(t):
	(r, g, b) = map(int, input().split())
	k = int(input())
	ans = 0
	flag = False
	if r - k < 0:
		ans += r
	else:
		ans += k
		flag = True
	if g - k < 0:
		ans += g
	else:
		ans += k
		if flag:
			ans -= 1
		flag = True
	if b - k < 0:
		ans += b
	else:
		ans += k
		if flag:
			ans -= 1
	print(ans)


for _ in range(int(input())):
	(r, g, b) = map(int, input().split())
	k = int(input())
	print(min(r, k - 1) + min(g, k - 1) + min(b, k - 1) + 1)


for t in range(int(input())):
	(r, g, b) = map(int, input().split())
	k = int(input())
	count = 0
	if r >= k - 1:
		count += k - 1
	else:
		count += r
	if g >= k - 1:
		count += k - 1
	else:
		count += g
	if b >= k - 1:
		count += k - 1
	else:
		count += b
	print(count + 1)


def min(a, b, c):
	if a <= b and a <= c:
		m = a
	elif b <= a and b <= c:
		m = b
	elif c <= a and c <= b:
		m = c
	return m

def min2(a, b):
	if a <= b:
		k = a
	else:
		k = b
	return k
T = int(input())
for i in range(T):
	x = input()
	k = int(input())
	x = x.split(' ')
	(r, g, b) = (int(x[0]), int(x[1]), int(x[2]))
	n = r + g + b
	m = min(r, g, b)
	if m == r:
		w = min2(g, b)
	elif m == g:
		w = min2(r, b)
	else:
		w = min2(r, g)
	if m >= k - 1:
		a = 3 * k - 2
	elif w >= k - 1:
		a = 3 * m + 2 * (k - m) - 1
	else:
		a = 3 * m + 2 * (w - m) + (k - w)
	print(a)


T = int(input())
while T > 0:
	T -= 1
	(R, G, B) = [int(i) for i in input().split()]
	k = int(input())
	count = min(R, k - 1)
	count += min(G, k - 1)
	count += min(B, k - 1)
	print(count + 1)


t = int(input())
for _ in range(t):
	(ri, gj, bo) = map(int, input().split())
	kf = int(input())
	print(min(ri, kf - 1) + min(gj, kf - 1) + min(bo, kf - 1) + 1)


def check_condition(count, k):
	return count == k
T = int(input())
if T < 1 or T > 1000:
	print('error')
else:
	for i in range(0, T):
		(r, g, b) = map(int, input().split())
		K = int(input())
		if r < 1 or r > 1000000000 or g < 1 or (g > 1000000000) or (b < 1) or (b > 1000000000):
			print('error')
		elif max([r, g, b]) < K or K < 1:
			print('error')
		else:
			minimum = min(r, g, b)
			draws = 0
			if K <= minimum:
				print(3 * (K - 1) + 1)
			else:
				draws = draws + 3 * minimum
				K = K - minimum
				r = r - minimum
				g = g - minimum
				b = b - minimum
				l = []
				if r != 0:
					l.append(r)
				if g != 0:
					l.append(g)
				if b != 0:
					l.append(b)
				minimum = min(l)
				if K <= minimum:
					draws = draws + len(l) * (K - 1) + 1
				else:
					draws = draws + len(l) * minimum
					K = K - minimum
					draws = draws + K
				print(draws)


n = int(input())
output = ''
for i in range(0, n):
	num_list = sorted(map(int, input().split(' ')))
	K = int(input())
	if K <= num_list[0]:
		output += f'{3 * K - 2}\n'
	elif num_list[0] < K <= num_list[1]:
		output += f'{num_list[0] + 2 * K - 1}\n'
	else:
		output += f'{num_list[0] + num_list[1] + K}\n'
print(output)


n = int(input())
for _ in range(n):
	l = list(map(int, input().split()))
	k = int(input())
	k = k - 1
	s = 0
	l.sort()
	o = len(l)
	for i in range(o):
		if l[i] > k:
			s = s + k * (o - i)
			break
		else:
			s = s + l[i]
	print(s + 1)


testcase = int(input())
while testcase:
	(r, g, b) = map(lambda x: int(x), input().split())
	k = int(input())
	print(min(k - 1, r) + min(k - 1, g) + min(k - 1, b) + 1)
	testcase -= 1


for _ in range(int(input())):
	a = list(map(int, input().split()))
	a.sort()
	k = int(input())
	if a[0] >= k:
		print((k - 1) * 3 + 1)
	elif a[0] < k <= a[1]:
		print(a[0] + (k - 1) * 2 + 1)
	else:
		print(a[0] + a[1] + k)


n = int(input())
for i in range(n):
	(r, g, b) = map(int, input().split())
	k = int(input())
	count = min(r, k - 1)
	count += min(g, k - 1)
	count += min(b, k - 1)
	print(count + 1)


t = int(input())
for i in range(t):
	(r, g, b) = [int(x) for x in input().split()]
	k = int(input())
	list1 = [r, g, b]
	if r >= k - 1 and g >= k - 1 and (b >= k - 1):
		print(k - 1 + k - 1 + k - 1 + 1)
	less = 0
	if r < k - 1:
		less = less + 1
	if g < k - 1:
		less = less + 1
	if b < k - 1:
		less = less + 1
	if less == 1:
		list1.sort()
		small = list1[0]
		print(small + k - 1 + k - 1 + 1)
	if less == 2:
		list1.sort()
		print(list1[0] + list1[1] + k)


for _ in range(int(input())):
	l = list(map(int, input().strip().split()))
	n = int(input())
	ans = 0
	for i in l:
		if i < n:
			ans += i
		else:
			ans += n - 1
	print(ans + 1)


for _ in range(int(input())):
	(R, G, B) = map(int, input().split())
	K = int(input())
	count = 0
	if R >= K:
		count += K - 1
	else:
		count += R
	if G >= K:
		count += K - 1
	else:
		count += G
	if B >= K:
		count += K - 1
	else:
		count += B
	print(count + 1)


for _ in range(int(input())):
	arr = [int(i) for i in input().split()]
	k = int(input())
	f = 0
	for i in range(3):
		f = f + min(arr[i], k - 1)
	print(f + 1)


for i in range(int(input())):
	balloons = [int(s) for s in str(input()).split()]
	min_number = int(input())
	res = 0
	for b in balloons:
		if b < min_number:
			res += b
		else:
			res += min_number - 1
	print(res + 1)


def main():
	for _ in range(int(input())):
		rgb = [int(x) for x in input().split()]
		k = int(input())
		ans = 0
		for i in range(3):
			ans += min(rgb[i], k - 1)
		print(ans + 1)
main()


trials = int(input())
for i in range(trials):
	balloons = [int(x) for x in input().split()]
	minimum = int(input())
	pulls = 0
	for i in balloons:
		pulls += i if i < minimum else minimum - 1
	pulls += 1
	print(pulls)


n = int(input())
for i in range(n):
	l = sorted(list(map(int, input().split())))
	(x, y, z) = l
	k = int(input())
	print(min(x, k - 1) + min(y, k - 1) + min(z, k - 1) + 1)


t = int(input())
for i in range(t):
	(a, b, c) = map(int, input().split())
	k = int(input())
	if a >= k:
		r = k - 1
	else:
		r = a
	if b >= k:
		g = k - 1
	else:
		g = b
	if c >= k:
		bb = k - 1
	else:
		bb = c
	print(r + g + bb + 1)


for _ in range(int(input())):
	(a, b, c) = map(int, input().split())
	k = int(input())
	maxy = max(a, b, c)
	print(k + min(k - 1, a) + min(k - 1, b) + min(k - 1, c) - min(k - 1, maxy))


for t in range(int(input())):
	x = list(map(int, input().split()))
	x.sort()
	k = int(input())
	s = sum(x)
	if k == 1:
		print(1)
	elif k <= x[0]:
		print(3 * k - 2)
	elif k <= x[1]:
		print(3 * x[0] + 2 * (k - x[0]) - 1)
	else:
		print(x[0] + x[1] + k)


for x in range(int(input())):
	stuff = list(map(int, input().split()))
	required = int(input())
	pulled = 0
	for times in range(3):
		pulled += min(stuff[times], required - 1)
	print(pulled + 1)


for _ in range(int(input())):
	color = list(map(int, input().split()))
	k = int(input())
	c = 0
	for i in range(3):
		c += min(color[i], k - 1)
	print(c + 1)


for i in range(int(input())):
	(r, g, b) = map(int, input().split())
	k = int(input())
	c = [r, g, b, k]
	c.sort()
	if c[0] == k:
		print(3 * (k - 1) + 1)
	elif c[1] == k:
		print(c[0] + 2 * (k - 1) + 1)
	elif c[2] == k:
		print(c[0] + c[1] + k)
	else:
		pass


num = int(input())
cases = [[input().split() for j in range(2)] for i in range(num)]
for case in cases:
	arr = map(int, case[0])
	arr = sorted(arr)
	color = int(case[1][0])
	r = min(arr[0], color - 1)
	g = min(arr[1], color - 1)
	b = min(arr[2], color - 1)
	print(r + g + b + 1)


for i in range(int(input())):
	bag = list(map(int, input().split()))
	bag.sort()
	k = int(input())
	if bag[0] >= k:
		balls = 3 * k - 2
	elif bag[1] >= k:
		balls = bag[0] + 2 * k - 1
	elif bag[2] >= k:
		balls = bag[0] + bag[1] + k
	else:
		pass
	print(balls)


t = int(input())
for v in range(0, t, 1):
	rgb = input()
	rgb = list(map(int, rgb.split(' ')))
	k = int(input())
	rgb.sort(reverse=True)
	if rgb[1] < k and rgb[2] < k:
		print(rgb[1] + rgb[2] + k)
	elif rgb[2] < k:
		print(rgb[2] + 2 * k - 1)
	else:
		print(3 * k - 2)


for i in range(int(input())):
	L = list(map(int, input().split()))
	N = int(input())
	SUM = 0
	for i in L:
		if i < N:
			SUM += i
		else:
			SUM += N - 1
	print(SUM + 1)


n = int(input())
for i in range(n):
	(a, b, c) = map(int, input().split())
	l = [a, b, c]
	l.sort()
	k = int(input())
	s = min(l[0], k - 1) + min(l[1], k - 1) + k
	print(s)


for _ in range(int(input())):
	(R, G, B) = map(int, input().split())
	K = int(input())
	ans = 3 * K - 2
	if R < K - 1:
		ans -= K - R - 1
	if G < K - 1:
		ans -= K - G - 1
	if B < K - 1:
		ans -= K - B - 1
	print(ans)


for _ in range(int(input())):
	(R, G, B) = map(int, input().split())
	lis = [R, G, B]
	lis.sort()
	k = int(input())
	s = min(lis[0], k - 1) + min(lis[1], k - 1) + k
	print(s)


for i in range(int(input())):
	(a, b, c) = map(int, input().split())
	ls = [a, b, c]
	ls.sort()
	k = int(input())
	if k == 1:
		print(1)
		continue
	if k <= min(ls):
		print(3 * k - 2)
	elif k <= ls[1]:
		print(ls[0] + 2 * k - 1)
	else:
		print(ls[0] + ls[1] + k)


def n_balloons(r, g, b, k):
	return sum((min(x, k - 1) for x in [r, g, b])) + 1
n_cases = int(input())
for _ in range(n_cases):
	(r, g, b) = (int(x) for x in input().split())
	k = int(input())
	print(n_balloons(r, g, b, k))


t = int(input())
for bunny in range(t):
	colors = list(map(int, input().split()))
	k = int(input())
	count = 0
	for i in colors:
		count += i if i < k else k - 1
	count += 1
	print(count)


for i in range(int(input())):
	co = list(map(int, input().split()))
	k = int(input())
	s = 0
	if k == 1:
		print(1)
	else:
		for i in co:
			if i >= k:
				s += k - 1
			else:
				s += i
		print(s + 1)


ntc = int(input())
for i in range(ntc):
	(r, g, b) = (int(x) for x in input().split())
	k = int(input())
	t = [r, g, b]
	if r < k or b < k or g < k:
		var_2 = [var_1 for var_1 in t if var_1 < k]
		if len(var_2) > 1:
			print(sum(var_2) + k)
		else:
			print(sum(var_2) + k - 1 + k)
	else:
		print(k - 1 + k - 1 + k)


for _ in range(int(input())):
	l = sorted([int(x) for x in input().split()])
	k = int(input())
	total = min(l[0], k - 1) + min(l[1], k - 1) + min(l[2], k - 1) + 1
	print(total)


from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	rgb = list(map(int, input().split()))
	k = int(input())
	r = 0
	for i in rgb:
		r += min(i, k - 1)
	print(r + 1)


T = int(input())
for i in range(0, T, 1):
	(r, g, b) = map(int, input().split())
	k = int(input())
	print(1 + min(k - 1, r) + min(k - 1, g) + min(k - 1, b))


T = int(input())
for i in range(T):
	(R, G, B) = input().split(' ')
	R = int(R)
	G = int(G)
	B = int(B)
	K = int(input())
	[mini, mede, maxi] = sorted([R, G, B])
	if K <= mini:
		print(3 * (K - 1) + 1)
	elif K <= mede:
		print(3 * mini + 2 * (K - mini - 1) + 1)
	elif K <= maxi:
		print(3 * mini + 2 * (mede - mini) + (K - mede))
	else:
		print('Not Possible')


testcases = int(input())
for _ in range(testcases):
	colors = list(map(int, input().split()))
	k = int(input())
	colors.sort()
	s = 0
	if k <= colors[0]:
		s += (k - 1) * 3 + 1
	elif k <= colors[1]:
		s += colors[0] * 3
		k -= colors[0]
		s += (k - 1) * 2 + 1
	else:
		s += colors[0] * 3
		s += (colors[1] - colors[0]) * 2
		k -= colors[1]
		s += k
	print(s)


from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	(a, b, c) = map(int, input().split())
	k = int(input())
	r = k - 1 if a >= k else a
	g = k - 1 if b >= k else b
	b_ = k - 1 if c >= k else c
	print(r + g + b_ + 1)


t = int(input())
for i in range(t):
	l = [int(x) for x in input().split()]
	k = int(input())
	ans = 0
	for i in range(3):
		ans = ans + min(l[i], k - 1)
	print(ans + 1)


for i in range(int(input())):
	balls = list(map(int, input().split()))
	n = int(input())
	total = 1
	for x in balls:
		if x < n:
			total += x
		else:
			total += n - 1
	print(total)


t = int(input())
for x in range(t):
	l = list(map(int, input().split()))
	l.sort()
	k = int(input())
	if l[0] < k:
		if l[1] < k:
			print(k * 3 - (k - l[0]) - (k - l[1]))
		else:
			print(k * 3 - (k - l[0]) - 1)
	else:
		print(k * 3 - 2)


T = int(input())
for i in range(T):
	rgb = list(map(int, input().split()))
	k = int(input())
	s = 0
	for j in sorted(rgb)[:-1]:
		if j >= k:
			s += k - 1
		else:
			s += j
	s += k
	print(s)


t = int(input())
for _ in range(t):
	ls = list(map(int, input().split()))
	k = int(input())
	ls.sort()
	ans = 3 * (k - 1) + 1
	if ls[0] < k - 1:
		ans = ans - (k - 1 - ls[0])
	if ls[1] < k - 1:
		ans = ans - (k - 1 - ls[1])
	if ls[2] < k - 1:
		ans = ans - (k - 1 - ls[2])
	print(ans)


for _ in range(int(input())):
	l = list(map(int, input().split()))
	n = int(input())
	if n > 1:
		l.sort()
	if n == 1:
		print(1)
	elif l[0] >= n:
		print((n - 1) * 3 + 1)
	elif l[1] >= n:
		print((n - 1 - l[0]) * 2 + l[0] * 3 + 1)
	else:
		print(l[0] + l[1] + n)


t = int(input())
for kyg in range(t):
	(r, g, b) = map(int, input().split())
	k = int(input())
	bal = [r, g, b]
	bal.sort()
	if k > bal[0]:
		if k > bal[1]:
			print(bal[0] + bal[1] + k)
		else:
			print(bal[0] + 2 * k - 1)
	else:
		print(3 * k - 2)


t = int(input())
while t > 0:
	(r, g, b) = map(int, input().split())
	k = int(input())
	k1 = k - 1
	tb = 0
	if k <= min(r, g, b):
		print(k1 * 3 + 1)
	else:
		co = list((r, g, b))
		co.sort()
		i = 0
		mb = 3
		while i <= 3:
			if k == 1:
				print(tb + 1)
				break
			else:
				if k <= co[i]:
					print((k - 1) * mb + tb + 1)
					break
				tb = tb + co[i] * mb
				k = k - co[i]
				for j in range(i + 1, 3):
					co[j] = co[j] - co[i]
				mb = mb - 1
				i += 1
	t = t - 1


def main():
	(r, g, b) = map(int, input().split())
	k = int(input())
	min1 = min(r, g, b)
	ans = 0
	if min1 >= k:
		ans = 3 * (k - 1) + 1
	else:
		ans = min1 * 3
		r = r - min1
		g = g - min1
		b = b - min1
		k = k - min1
		min1 = int(1000000000.0)
		count = 0
		if r != 0:
			min1 = min(r, min1)
			count += 1
		if g != 0:
			min1 = min(g, min1)
			count += 1
		if b != 0:
			min1 = min(b, min1)
			count += 1
		if min1 >= k:
			ans += 2 * (k - 1) + 1 if count == 2 else k
		else:
			ans += min1 * 2
			r = r - min1
			g = g - min1
			b = b - min1
			k = k - min1
			ans += k
	print(ans)
for _ in range(int(input())):
	main()


t = int(input())
for i in range(t):
	(R, G, B) = map(int, input().split())
	K = int(input())
	if R >= K:
		r = K - 1
	else:
		r = R
	if G >= K:
		g = K - 1
	else:
		g = G
	if B >= K:
		b = K - 1
	else:
		b = B
	print(r + g + b + 1)


for _ in range(int(input())):
	l = list(map(int, input().split()))
	k = int(input())
	c = 0
	for i in l:
		c += min(i, k - 1)
	print(c + 1)


t = int(input())
for i in range(t):
	l = list(map(int, input().split()))
	k = int(input())
	l.sort()
	ans = 0
	cnt = 0
	for i in l:
		if k > i:
			ans += i
		else:
			cnt += 1
	print(ans + cnt * (k - 1) + 1)


t = int(input())
while t != 0:
	(a, b, c) = [int(i) for i in input().split()]
	n = int(input())
	print(1 + min(n - 1, a) + min(n - 1, b) + min(n - 1, c))
	t = t - 1


tries = int(input(''))
for i in range(1, tries + 1):
	(red, blue, green) = [int(x) for x in input('').split()]
	n = int(input(''))
	l1 = [red, blue, green]
	max = red
	for a in l1:
		if max < a:
			max = a
	l1.remove(max)
	if n == 1:
		attempts = 1
	elif l1[0] > l1[1]:
		secondmax = l1[0]
		if l1[0] >= n:
			if l1[1] >= n:
				attempts = 3 * n - 2
			else:
				attempts = 2 * n - 1 + l1[1]
		else:
			attempts = n + l1[0] + l1[1]
	else:
		secondmax = l1[1]
		if l1[1] >= n:
			if l1[0] >= n:
				attempts = 3 * n - 2
			else:
				attempts = 2 * n - 1 + l1[0]
		else:
			attempts = n + l1[0] + l1[1]
	print(attempts)


for t in range(int(input())):
	rgb = [int(i) for i in input().split()]
	k = int(input()) - 1
	tot = 1
	for i in range(3):
		tot += min(k, rgb[i])
	print(tot)


t = int(input())
for i in range(t):
	l = input().split(' ')
	k = int(input())
	l[0] = int(l[0])
	l[1] = int(l[1])
	l[2] = int(l[2])
	l.sort()
	if k == 1:
		print(1)
	elif l[1] < k:
		print(l[0] + l[1] + k)
	elif l[0] < k:
		print(2 * k - 1 + l[0])
	else:
		print(3 * k - 2)


t = int(input())
for i in range(t):
	colors = [int(x) for x in input().split()]
	k = int(input())
	sorted_color = sorted(colors)
	finalcount = 0
	for i in sorted_color:
		if i < k:
			finalcount += i
		elif i >= k:
			finalcount += k - 1
	finalcount += 1
	print(finalcount)


t = int(input())
for i in range(t):
	(r, g, b) = map(int, input().split())
	k = int(input())
	print(min(k - 1, r) + min(k - 1, g) + min(k - 1, b) + 1)


a = int(input())
for i in range(a):
	l = list(map(int, input().split()))
	r = int(input())
	l.sort()
	cnt = 0
	need = 0
	for j in l:
		if j < r:
			need = need + j
		else:
			cnt = cnt + 1
	print(need + cnt * (r - 1) + 1)


t = int(input())
for i in range(t):
	rgb = list(map(int, input().split()))
	k = int(input())
	num = min(rgb[0], k - 1) + min(rgb[1], k - 1) + min(rgb[2], k - 1) + 1
	print(num)