Chef has a garden containing N cells. The i-th cell has R_{i} red flowers and B_{i} blue flowers. Chef can collect only one type of flowers (either red or blue) from each cell.

Let X denote the total number of red flowers Chef collects and Y denote the total number of blue flowers Chef collects. Chef wants to maximize the value of \mathrm{min}(X, Y). Can you help Chef?

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

- The first line contains a single integer T — the number of test cases. Then the test cases follow.
- The first line of each test case contains an integer N — the number of cells in Chef's garden.
- The second line of each test case contains N space-separated integers R_{1}, R_{2}, \dots, R_{N} denoting the number of red flowers in each cell.
- The third line of each test case contains N space-separated integers B_{1}, B_{2}, \dots, B_{N} denoting the number of blue flowers in each cell.

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

For each test case, output the maximum value of \mathrm{min}(X, Y).

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

$1 ≤ T ≤ 100$
$1 ≤ N ≤ 100$
$1 ≤ R_{i}, B_{i} ≤ 200$
- The sum of $N$ over all test cases does not exceed $100$.

----- Sample Input 1 ------ 
3
1
101
3
2
1 200
199 1
4
1 2 3 10
3 1 3 5

----- Sample Output 1 ------ 
0
199
7

----- explanation 1 ------ 
Test case 1:
If Chef collects $101$ red flowers from the cell, Chef will have a total of $101$ red flowers $(X = 101)$ and $0$ blue flowers $(Y = 0)$. 
If Chef collects the $3$ blue flowers from the cell, Chef will have a total of $0$ red flowers $(X = 0)$ and $3$ blue flowers $(Y = 3)$. 
Either way, $\mathrm{min}(X, Y) = 0$, the answer is $0$.

Test case 2: Chef collects the $199$ blue flowers from the first cell and the $200$ red flowers from the second cell, so $\mathrm{min}(X, Y) = 199$, which is maximum.

Test case 3: Chef collects blue cells from the first three cells $(Y = 3 + 1 + 3)$ and red flowers from the fourth cell $(X = 10)$, so $\mathrm{min}(X, Y) = 7$, which is maximum.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Dynamic programming


Solutions:
for _ in range(int(input())):
	n = int(input())
	ri = list(map(int, input().split()))
	bi = list(map(int, input().split()))
	s = sum(ri)
	dp = [[-1 for i in range(s + 1)] for j in range(n)]
	dp[0][0] = bi[0]
	dp[0][ri[0]] = 0
	for i in range(n - 1):
		for j in range(s + 1):
			if dp[i][j] != -1:
				dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + bi[i + 1])
				dp[i + 1][j + ri[i + 1]] = max(dp[i + 1][j + ri[i + 1]], dp[i][j])
	ans = 0
	for i in range(s + 1):
		if dp[n - 1][i] != -1:
			ans = max(ans, min(i, dp[n - 1][i]))
	print(ans)


for _ in range(int(input())):
	n = int(input())
	r = list(map(int, input().strip().split()))
	b = list(map(int, input().strip().split()))
	sb = sum(b)
	sr = sum(r)
	x = [-1 for i in range(sr + 1000)]
	x[0] = sb
	for i in range(len(r)):
		for j in range(len(x) - 1, -1, -1):
			if x[j] != -1:
				x[j + r[i]] = max(x[j + r[i]], x[j] - b[i])
	m = 0
	for i in range(len(x)):
		m = max(m, min(i, x[i]))
	print(m)


from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	n = int(input())
	r = list(map(int, input().split()))
	b = list(map(int, input().split()))
	d = {sum(r): 0}
	for i in range(n):
		aux = dict(d)
		for sr in d:
			(x, y) = (sr - r[i], d[sr] + b[i])
			if x in aux:
				aux[x] = max(aux[x], y)
			else:
				aux[x] = y
		d = dict(aux)
	ans = 0
	for (sr, sb) in d.items():
		ans = max(ans, min(sr, sb))
	print(ans)


for _ in range(int(input())):
	n = int(input())
	reds = list(map(int, input().split()))
	blues = list(map(int, input().split()))
	su = min(sum(reds), sum(blues))
	dp = [-10 ** 10 for _ in range(su + 1)]
	dp[0] = 0
	for i in range(n):
		for j in range(su, -1, -1):
			dp[j] = max(dp[j], dp[j] + blues[i])
			if j >= reds[i]:
				dp[j] = max(dp[j], dp[j - reds[i]])
	ans = max([min(i, dp[i]) for i in range(su + 1)])
	print(ans)


for _ in range(int(input())):
	n = int(input())
	r = list(map(int, input().split()))
	b = list(map(int, input().split()))
	maxS = 20004
	dp = [-1] * maxS
	dp[0] = 0
	for i in range(n):
		(R, B) = (r[i], b[i])
		for x in reversed(range(maxS)):
			val = -1
			if dp[x] != -1:
				val = dp[x] + B
			if x - R >= 0 and dp[x - R] != -1:
				val = max(val, dp[x - R])
			dp[x] = val
	ans = 0
	for i in range(maxS):
		if dp[i] == -1:
			continue
		ans = max(ans, min(i, dp[i]))
	print(ans)


for _ in range(int(input())):
	z = int(input())
	o = list(map(int, input().split()))
	c = list(map(int, input().split()))
	maxS = 20004
	dp = [-1] * maxS
	dp[0] = 0
	for i in range(z):
		(R, B) = (o[i], c[i])
		for x in reversed(range(maxS)):
			val = -1
			if dp[x] != -1:
				val = dp[x] + B
			if x - R >= 0 and dp[x - R] != -1:
				val = max(val, dp[x - R])
			dp[x] = val
	ans = 0
	for j in range(maxS):
		if dp[j] == -1:
			continue
		ans = max(ans, min(j, dp[j]))
	print(ans)


def knapsack(dp, cnt_red, red, blue):

	def recur(ind, red_wanted):
		nonlocal dp
		if (ind, red_wanted) in dp:
			return dp[ind, red_wanted]
		if ind == len(red):
			if red_wanted > 0:
				dp[ind, red_wanted] = -float('inf')
			else:
				dp[ind, red_wanted] = 0
		elif red_wanted <= 0:
			s = 0
			for i in range(ind, len(red)):
				s += blue[i]
			dp[ind, red_wanted] = s
		else:
			dp[ind, red_wanted] = max(recur(ind + 1, red_wanted - red[ind]), recur(ind + 1, red_wanted) + blue[ind])
		return dp[ind, red_wanted]
	blue_cnt = recur(0, cnt_red)
	return blue_cnt
for t in range(int(input())):
	n = int(input())
	red = [int(x) for x in input().split(' ')]
	blue = [int(x) for x in input().split(' ')]
	high = sum(red)
	low = 0
	dp = {}
	maxx = 0
	while low <= high:
		mid = (low + high) // 2
		temp_b = knapsack(dp, mid, red, blue)
		if temp_b < mid:
			high = mid - 1
		elif temp_b > mid:
			low = mid + 1
		else:
			maxx = max(maxx, temp_b)
			break
		maxx = max(maxx, min(temp_b, mid))
	print(maxx)


for tt in range(int(input())):
	nn = int(input())
	red = [int(x) for x in input().split(' ')]
	blue = [int(x) for x in input().split(' ')]
	max_Sum = 200 * 100 + 10
	dp = [-1] * max_Sum
	dp[0] = 0
	for i in range(nn):
		for j in range(max_Sum - 1, -1, -1):
			if j + red[i] < max_Sum:
				dp[j + red[i]] = max(dp[j + red[i]], dp[j])
			if dp[j] >= 0:
				dp[j] += blue[i]
	res = 0
	for i in range(max_Sum):
		res = max(res, min(i, dp[i]))
	print(res)


for trie in range(int(input())):
	N = int(input())
	red = list(map(int, input().split()))
	blue = list(map(int, input().split()))
	max_sum = 200 * 100 + 10
	dp = [-1] * max_sum
	dp[0] = 0
	for i in range(N):
		for j in range(max_sum - 1, -1, -1):
			if j + red[i] < max_sum:
				dp[j + red[i]] = max(dp[j + red[i]], dp[j])
			if dp[j] >= 0:
				dp[j] += blue[i]
	result = 0
	for i in range(max_sum):
		result = max(result, min(i, dp[i]))
	print(result)


ans = []
nq = int(input())
for _ in range(nq):
	n = int(input())
	R = list(map(int, input().split()))
	B = list(map(int, input().split()))
	x = sum(R) + 1
	best = []
	for i in range(x):
		best.append([-1] * n)
	best[R[0]][0] = 0
	best[0][0] = B[0]
	for j in range(1, n):
		for i in range(x):
			bPick = -1
			if j - 1 >= 0 and best[i][j - 1] != -1:
				bPick = best[i][j - 1] + B[j]
			rPick = -1
			if i - R[j] >= 0 and best[i - R[j]][j - 1] != -1:
				rPick = best[i - R[j]][j - 1]
			best[i][j] = max(rPick, bPick)
	val = 0
	for i in range(x):
		val = max(val, min(i, best[i][n - 1]))
	ans.append(val)
print(*ans, sep='\n')


import sys
import math
import collections
import random
from heapq import heappush, heappop
from functools import reduce
input = lambda : sys.stdin.readline().rstrip('\r\n')
ints = lambda : list(map(int, input().split()))

def solve() -> None:
	n = int(input())
	R = ints()
	B = ints()
	mx = 200 * n + 4
	dp = [-1] * mx
	dp[0] = 0
	for (r, b) in zip(R, B):
		for x in reversed(range(mx)):
			val = -1
			if dp[x] != -1:
				val = dp[x] + b
			if x - r >= 0 and dp[x - r] != -1:
				val = max(val, dp[x - r])
			dp[x] = val
	ans = 0
	for i in range(mx):
		if dp[i] == -1:
			continue
		ans = max(ans, min(i, dp[i]))
	print(ans)
t = int(input())
for _ in range(t):
	solve()


import sys

def input():
	return sys.stdin.readline().strip()
t = int(input())
for _ in range(t):
	n = int(input())
	r = list(map(int, input().split()))
	b = list(map(int, input().split()))
	dp = [-1] * (200 * n + 1)
	dp[0] = 0
	for i in range(n):
		for j in range(200 * n, -1, -1):
			dp[j] = max(dp[j - r[i]] if j - r[i] >= 0 else -1, dp[j] + b[i] if dp[j] != -1 else -1)
	ans = 0
	for i in range(200 * n + 1):
		ans = max(ans, min(i, dp[i]))
	sys.stdout.write(str(ans) + '\n')


for t in range(int(input())):
	n = int(input())
	red = [int(x) for x in input().split(' ')]
	blue = [int(x) for x in input().split(' ')]
	maxSum = 200 * 100 + 10
	dp = [-1] * maxSum
	dp[0] = 0
	for i in range(n):
		for j in range(maxSum - 1, -1, -1):
			if j + red[i] < maxSum:
				dp[j + red[i]] = max(dp[j + red[i]], dp[j])
			if dp[j] >= 0:
				dp[j] += blue[i]
	res = 0
	for i in range(maxSum):
		res = max(res, min(i, dp[i]))
	print(res)


for T in range(int(input())):
	n = int(input())
	red = list(map(int, input().split()))
	blue = list(map(int, input().split()))
	mx = 200 * 100 + 10
	dp = [-1] * mx
	dp[0] = 0
	for i in range(n):
		for j in range(mx - 1, -1, -1):
			if j + red[i] < mx:
				dp[j + red[i]] = max(dp[j + red[i]], dp[j])
			if dp[j] >= 0:
				dp[j] += blue[i]
	ans = 0
	for i in range(mx):
		ans = max(ans, min(dp[i], i))
	print(ans)


import sys
input = sys.stdin.readline
from math import sqrt
from collections import defaultdict
from heapq import heappop, heappush

def I():
	return list(map(int, input().split()))
for _ in range(int(input())):
	n = int(input())
	red = I()
	blue = I()
	dp = [-1] * (sum(red) + 1)
	dp[sum(red)] = 0
	for i in range(n):
		for j in range(len(dp)):
			if j + red[i] >= len(dp):
				break
			if dp[j + red[i]] != -1:
				dp[j] = max(dp[j], dp[j + red[i]] + blue[i])
	ans = 0
	for i in range(len(dp)):
		ans = max(ans, min(i, dp[i]))
	print(ans)


for _ in range(int(input())):
	n = int(input())
	red = list(map(int, input().split()))
	blue = list(map(int, input().split()))
	r = sum(red)
	dp = [[float('inf')] * (sum(red) + 1) for i in range(n + 1)]
	for i in range(n + 1):
		dp[i][0] = 0
	for i in range(1, n + 1):
		for j in range(1, r + 1):
			r1 = red[i - 1]
			dp[i][j] = min(dp[i - 1][j], dp[i][j])
			if j >= r1:
				dp[i][j] = min(dp[i][j], dp[i - 1][j - r1] + blue[i - 1])
	dp1 = [[float('inf') * -1] * (sum(red) + 1) for i in range(n + 1)]
	for i in range(n + 1):
		dp1[i][0] = 0
	for i in range(1, n + 1):
		for j in range(1, r + 1):
			r1 = red[i - 1]
			dp1[i][j] = max(dp1[i - 1][j], dp1[i][j])
			if j >= r1:
				dp1[i][j] = max(dp1[i][j], dp1[i - 1][j - r1] + blue[i - 1])
	ans = 0
	for i in range(r + 1):
		if dp[n][i] == float('inf') and dp1[n][i] == float('inf') * -1:
			continue
		ans = max(ans, min(i, sum(blue) - dp[n][i]))
	print(ans)


from sys import stdin
input = stdin.readline

def knapsack(W, weight, value):
	n = len(weight)
	A = [[0] * (W + 1) for i in range(n + 1)]
	for i in range(1, n + 1):
		for w in range(W + 1):
			if weight[i - 1] > w:
				A[i][w] = A[i - 1][w]
			else:
				A[i][w] = max(A[i - 1][w], A[i - 1][w - weight[i - 1]] + value[i - 1])
	return A[n][W]

def possible(N, target):
	return knapsack(sum(R) - target, R, B) >= target

def solve(N):
	if N == 1:
		return 0
	(inf, sup) = (0, min(sum(R), sum(B)))
	ans = 0
	while inf <= sup:
		mid = (inf + sup) // 2
		if possible(N, mid):
			ans = mid
			inf = mid + 1
		else:
			sup = mid - 1
	return ans
T = int(input().strip())
for problem in range(1, T + 1):
	N = int(input().strip())
	R = [int(x) for x in input().strip().split()]
	B = [int(x) for x in input().strip().split()]
	print(solve(N))


def mi():
	return map(int, input().split())

def li():
	return list(mi())

def si():
	return str(input())

def ni():
	return int(input())
import sys
sys.setrecursionlimit(1000000)

def solve(r, b, x, y, i):
	global dict
	if (x - y, i) in dp:
		return dp[x - y, i]
	if i >= len(r):
		return min(x, y)
	ans = max(solve(r, b, x + r[i] - y, 0, i + 1) + y, solve(r, b, x - (y + b[i]), 0, i + 1) + y + b[i])
	dp[x - y, i] = ans
	return ans
for _ in range(int(input())):
	n = int(input())
	r = li()
	b = li()
	dp = dict()
	print(solve(r, b, 0, 0, 0))


def dp(r, b, sb, i, x, memo):
	memokey = (i, x)
	if memokey in memo:
		return memo[memokey]
	if i >= len(r):
		return 0
	result = dp(r, b, sb, i + 1, x - b[i], memo)
	if sb[i + 1] >= x:
		result = max(result, dp(r, b, sb, i + 1, x, memo) + r[i])
	memo[memokey] = result
	return result
for _ in range(int(input())):
	n = int(input())
	r = list(map(int, input().split()))
	b = list(map(int, input().split()))
	sb = [0]
	for x in reversed(b):
		sb.append(sb[-1] + x)
	sb = sb[::-1]
	memo = dict()
	result = 0
	for x in range(1, sb[0]):
		result = max(min(x, dp(r, b, sb, 0, x, memo)), result)
	print(result)


t = int(input())
for _ in range(t):
	n = int(input())
	r = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	d = {sum(r): 0}
	for i in range(n):
		e = dict(d)
		for j in d:
			(p, q) = (j - r[i], d[j] + b[i])
			if p in e:
				e[p] = max(e[p], q)
			else:
				e[p] = q
		d = dict(e)
	ans = 0
	for i in d:
		ans = max(ans, min(i, d[i]))
	print(ans)


from sys import stdin
inf = -float('inf')
input = stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	dp = [0] + [inf] * sum(a)
	for i in range(n):
		for j in range(len(dp) - a[i] - 1, -1, -1):
			dp[j + a[i]] = max(dp[j + a[i]], dp[j])
			dp[j] = max(dp[j], dp[j] + b[i])
	ans = 0
	for i in range(len(dp)):
		ans = max(ans, min(i, dp[i]))
	print(ans)