You are given two arrays A and B, both of length N.

You would like to choose exactly K distinct indices i_{1},i_{2}, \ldots, i_{K} such that \min(A_{i_{1}}+A_{i_{2}}+ \ldots + A_{i_{K}}, B_{i_{1}}+B_{i_{2}}+\ldots + B_{i_{K}}) is maximized. Find this maximum value.

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

- The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follows.
- Each test case consists of 3 lines of input.
- The first line of each test case contains two space-separated integers N and K.
- The second line contains N space-separated integers A_{1}, A_{2}, \ldots, A_{N} denoting the elements of A.
- The third line contains N space-separated integers B_{1}, B_{2}, \ldots, B_{N} denoting the elements of B.

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

For each test case, output a new line containing one integer — the required maximum value.

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

$1 ≤ T ≤ 20$
$2 ≤ N ≤ 40$
$1 ≤ K ≤ N$
$1 ≤ A_{i}, B_{i} ≤ 40$

----- Sample Input 1 ------ 
3
5 3
4 2 3 1 4
3 2 5 5 1
4 2
1 2 3 4
4 3 2 1
6 3
8 10 3 6 7 2
4 8 4 1 1 6

----- Sample Output 1 ------ 
9
5
18

----- explanation 1 ------ 
Test Case $1$: One optimal choice of indices is $i_{1} = 1, i_{2} = 3, i_{3} = 5$. This gives $A_{1} + A_{3} + A_{5} = 11$ and $B_{1} + B_{3} + B_{5} = 9$.

Test Case $2$: One optimal choice of indices is $i_{1} = 1, i_{2} = 4$.

Test Case $3$: One optimal choice of indices is $i_{1} = 1, i_{2} = 2, i_{3} = 6$.

Difficulty: VERY_HARD
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
def dp(n, k, a, b):
	dp = [[-1 for _ in range(1601)] for __ in range(k + 1)]
	dp[0][0] = 0
	for i in range(n):
		for j in range(k - 1, -1, -1):
			for s in range(1601):
				if dp[j][s] != -1:
					dp[j + 1][s + a[i]] = max(dp[j][s] + b[i], dp[j + 1][s + a[i]])
	ans = 0
	for s in range(0, 1601):
		ans = max(ans, min(s, dp[k][s]))
	return ans
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = [int(i) for i in input().split()]
	b = [int(i) for i in input().split()]
	print(dp(n, k, a, b))


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	M = max(sum(A), sum(B)) + 1
	dp = [[-1 for s in range(M)] for i in range(K + 1)]
	dp[0][0] = 0
	for i in range(N):
		for j in range(K - 1, -1, -1):
			for s in range(M):
				s1 = s + A[i]
				if dp[j][s] != -1:
					dp[j + 1][s1] = max(dp[j + 1][s1], B[i] + dp[j][s])
	minmax = 0
	for s in range(M):
		minmax = max(minmax, min(s, dp[K][s]))
	print(minmax)


import sys
import bisect
from bisect import bisect_left as lb
from bisect import bisect_right as rb
input_ = lambda : sys.stdin.readline().strip('\r\n')
from math import log
from math import gcd
from math import atan2, acos
from random import randint
sa = lambda : input_()
sb = lambda : int(input_())
sc = lambda : input_().split()
sd = lambda : list(map(int, input_().split()))
sflo = lambda : list(map(float, input_().split()))
se = lambda : float(input_())
sf = lambda : list(input_())
flsh = lambda : sys.stdout.flush()
mod = 10 ** 9 + 7
mod1 = 998244353
gp = []
cost = []
dp = []
mx = []
ans1 = []
ans2 = []
special = []
specnode = []
a = 0
kthpar = []

def dfs2(root, par):
	if par != -1:
		dp[root] = dp[par] + 1
	for i in range(1, 20):
		if kthpar[root][i - 1] != -1:
			kthpar[root][i] = kthpar[kthpar[root][i - 1]][i - 1]
	for child in gp[root]:
		if child == par:
			continue
		kthpar[child][0] = root
		dfs(child, root)
ans = 0
a = []
(n, k) = (0, 0)
b = []
vis = []
tot = 0
time = []
time1 = []
adj = []
mx = -1
eps = 1e-07
gp = []
ans = []

def update_it(bit, i, val):
	n = len(bit)
	while i < n:
		bit[i] += val
		i += i & -i

def get_ans(bit, i):
	n = len(bit)
	tot = 0
	while i > 0:
		tot += bit[i]
		i -= i & -i
	return tot

def flip(a, l, r):
	for i in range(l, r):
		a[i] = '0' if a[i] == '1' else '1'
	return

def hnbhai(tc):
	(n, k) = sd()
	a = sd()
	b = sd()
	mx = sum(a) + 5
	dp = [[0 for i in range(mx)] for j in range(k + 1)]
	for i in range(n):
		for j in range(k, 0, -1):
			for s in range(mx - 1, 0, -1):
				if s - a[i] < 0:
					continue
				if j - 1 == 0 and s - a[i] == 0 or dp[j - 1][s - a[i]] != 0:
					dp[j][s] = max(dp[j][s], dp[j - 1][s - a[i]] + b[i])
	ans = 0
	for i in range(mx):
		ans = max(ans, min(i, dp[k][i]))
	print(ans)
for _ in range(sb()):
	hnbhai(_ + 1)