Given an array of integers and a target sum, determine the sum nearest to but not exceeding the target that can be created.  To create the sum, use any element of your array zero or more times.

For example, if $arr=[2,3,4]$ and your target sum is $10$, you might select $[2,2,2,2,2],[2,2,3,3]$ or $[3,3,3,1]$.  In this case, you can arrive at exactly the target.  

Function Description  

Complete the unboundedKnapsack function in the editor below.  It must return an integer that represents the sum nearest to without exceeding the target value.  

unboundedKnapsack has the following parameter(s):  

k: an integer  
arr: an array of integers  

Input Format

The first line contains an integer $\boldsymbol{\boldsymbol{t}}$, the number of test cases.    

Each of the next $\boldsymbol{\boldsymbol{t}}$ pairs of lines are as follows: 

- The first line contains two integers $n$ and $\boldsymbol{\mbox{k}}$, the length of $\textbf{arr}$ and the target sum. 

-  The second line contains $n$ space separated integers $arr\left[i\right]$. 

Constraints

$1\leq t\leq10$ 

$1\leq n,k,ar r[i]\leq2000$  

Output Format

Print the maximum sum for each test case which is as near as possible, but not exceeding, to the target sum on a separate line.

Sample Input
2
3 12
1 6 9
5 9
3 4 4 4 8

Sample Output
12
9

Explanation

In the first test case, one can pick {6, 6}. In the second, we can pick {3,3,3}.

Difficulty: MEDIUM
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
t = int(input())
for _ in range(t):
	lst = [int(i) for i in input().split()]
	goal = lst[1]
	nums = [int(i) for i in input().split()]
	dyno = [0]
	dyno += [-1] * goal
	for i in range(len(dyno)):
		tmp = -1
		largest_x = -1
		val = 0
		for x in nums:
			if i - x >= 0 and dyno[i - x] + x >= val:
				tmp = i - x
				largest_x = x
				val = dyno[i - x] + x
		if tmp < 0:
			dyno[i] = 0
		else:
			dyno[i] = largest_x + dyno[tmp]
	print(dyno[-1])


import sys
sys.setrecursionlimit(3000)
N = int(input())

def f(limit, list, total, dict):
	a = dict.get(total, -1)
	if a != -1:
		return a
	if total == limit:
		dict[total] = total
		return total
	if total > limit:
		dict[total] = 0
		return 0
	m = 0
	for el in list:
		m = max(m, f(limit, list, total + el, dict))
	if total > m:
		m = total
	dict[total] = m
	return m
for n in range(N):
	s = input().split()
	s = list(map(int, s))
	s2 = input().split()
	s2 = list(map(int, s2))
	d = {}
	print(f(s[1], s2, 0, d))


import sys
sys.setrecursionlimit(10000)

def is_possible(n, D):
	if n in D:
		return D[n]
	else:
		for i in range(1, n // 2 + 1):
			if is_possible(i, D) and is_possible(n - i, D):
				D[n] = True
				return True
		D[n] = False
		return False
for i in range(int(input())):
	k = int(input().split(' ')[1])
	D = {}
	for i in input().split(' '):
		D[int(i)] = True
	while not is_possible(k, D) and k > 0:
		k -= 1
	print(k)


def findAnswer(A, k, s, ans):
	if A[k][s] == 0:
		return
	if A[k][s] == A[k - 1][s]:
		findAnswer(A, k - 1, s, ans)
	else:
		findAnswer(A, k - 1, s - W[k], ans)
		ans.append(W[k])
T = int(input())
for n in range(T):
	(N, K) = (int(x) for x in input().split())
	W = [int(x) for x in input().split(' ', N)]
	A = [[0 for x in range(K + 1)] for y in range(N)]
	for k in range(0, N):
		for s in range(0, K + 1):
			A[k][s] = A[k - 1][s]
			for l in range(s // W[k], 0, -1):
				A[k][s] = max(A[k][s], A[k - 1][s - l * W[k]] + W[k] * l)
	ans = list()
	print(A[k][s])


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	W = list(map(int, input().split()))
	V = [0] * (4000 + 1)
	V[0] = 1
	best = 0
	for i in range(k):
		if V[i] == 1:
			for j in W:
				V[i + j] = 1
				if i + j <= k:
					best = max(best, i + j)
	print(best)


for T in range(int(input())):
	(n, k) = map(int, input().split())
	(ar, dp) = (sorted([int(i) for i in input().split()]), [0] * 2001)
	for i in range(1, k + 1):
		for j in ar:
			if j <= i:
				dp[i] = max(dp[i], j + dp[i - j])
	print(dp[k])


import sys
from heapq import *

def inp():
	return list(map(int, input().split()))

def f(a, k):
	a.insert(0, 0)
	x = len(a)
	y = k + 1
	m = [[0 for _ in range(y)] for _ in range(x)]
	for i in range(1, x):
		for j in range(1, y):
			m[i][j] = j - j % a[i]
			if m[i][j] == j:
				continue
			i_weight = 0
			while i_weight < j:
				m[i][j] = max(m[i][j], m[i - 1][j - i_weight] + i_weight)
				i_weight += a[i]
	return m[x - 1][y - 1]
t = int(input())
for _ in range(t):
	(n, k) = inp()
	a = inp()
	ans = f(a, k)
	print(ans)


T = int(input())
for i in range(T):
	(n, k) = list(map(int, input().split(' ')))
	nums = list(map(int, input().split(' ')))
	p = [-1 for j in range(k + 1)]
	p[0] = 0
	max = 0
	for j in range(k + 1):
		if p[j] > -1:
			for num in nums:
				if j + num <= k:
					p[j + num] = j
					if j + num > max:
						max = j + num
	print(max)


numinputs = int(input())
for dummy in range(numinputs):
	[n, k] = [int(val) for val in input().split()]
	vals = [int(val) for val in input().split()]
	vals = sorted(vals)
	dp = [0] * 2001
	for i in range(1, k + 1):
		for val in vals:
			if val > i:
				continue
			dp[i] = max(dp[i], val + dp[i - val])
	print(dp[k])


from collections import Counter

def bestSum(numbers, goal):
	sortedNumbers = sorted(set(numbers), reverse=True)
	return sum(bestMultiset(sortedNumbers, goal).elements())

def bestMultiset(sortedNumbers, goal):
	if len(sortedNumbers) > 1:
		bestSum = 0
		bestSet = Counter({})
		for i in range(0, goal // sortedNumbers[0] + 1):
			multiset = bestMultiset(sortedNumbers[1:], goal - i * sortedNumbers[0])
			multiset[sortedNumbers[0]] = i
			multisum = sum(multiset.elements())
			if bestSum < multisum <= goal:
				bestSum = multisum
				bestSet = multiset
		return +bestSet
	else:
		return Counter({sortedNumbers[0]: goal // sortedNumbers[0]})
for _ in range(int(input())):
	(numCount, goal) = [int(x) for x in input().split(' ')]
	numbers = [int(x) for x in input().split(' ')]
	print(bestSum(numbers, goal))


import sys, itertools
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	vec = sorted(map(int, input().split()))
	msum = 0
	mask = [False] * (k + 1)
	mask[0] = True
	for i in range(1, k + 1):
		for j in vec:
			if i - j >= 0 and mask[i - j] == True:
				mask[i] = True
				msum = i
				break
	print(msum)


def knapsack(space, arr, cache):
	if space in cache:
		return cache[space]
	best = 0
	for el in [e for e in arr if e <= space]:
		fill = knapsack(space - el, arr, cache) + el
		best = max(best, fill)
	cache[space] = best
	return best

def knapsack2(space, arr):
	old = set()
	best = 0
	new_solutions = [0]
	while new_solutions:
		best = max(best, max(new_solutions))
		old = old.union(new_solutions)
		old_solutions = new_solutions
		new_solutions = []
		for sol in old_solutions:
			new_solutions += [sol + e for e in arr if sol + e <= space and sol + e not in old]
	return best

def solve_case():
	(n, k) = [int(s) for s in input().split()]
	arr = [int(s) for s in input().split()]
	arr = list(set(arr))
	print(knapsack2(k, arr))
for _ in range(int(input())):
	solve_case()


cases = int(input())
for _ in range(cases):
	(n, cap) = [int(x) for x in input().split()]
	nums = [int(x) for x in input().split() if int(x) <= cap]
	combinations = []
	for num in nums:
		mult = 2
		while num * mult <= cap:
			combinations.append(num * mult)
			mult += 1
	nums += combinations
	nums = set(nums)
	nums = sorted(nums)
	configs = []
	for i in range(len(nums)):
		valids = [x for x in configs if x + nums[i] <= cap]
		if valids:
			configs.append(max(valids) + nums[i])
			configs.append(nums[i])
		else:
			configs.append(nums[i])
	if configs:
		print(max(configs))
	else:
		print(0)


import sys
case_count = int(input())
for i in range(case_count):
	(n, k) = [int(j) for j in input().split()]
	item = [int(j) for j in input().split()]
	exist = [False for i in range(k + 1)]
	exist[0] = True
	for i in range(1, k + 1):
		for j in item:
			if j <= i:
				if exist[i - j]:
					exist[i] = True
					break
	i = k
	multsum = 0
	while i > 0:
		if exist[i]:
			multsum = i
			break
		i -= 1
	print(multsum)


INF = 2000 ** 2
T = int(input())
for _ in range(T):
	(n, k) = map(int, input().split())
	ws = [x for x in map(int, input().split())]
	a = [-1] * 2001
	for kk in range(k + 1):
		best = 0
		for w in ws:
			if kk - w == 0:
				best = w
			elif kk - w > 0:
				best = max(best, w + a[kk - w])
		a[kk] = best
	print(a[k])


def max_multisum(numbers, k):
	ks = [0] * (k + 1)
	for (i, _) in enumerate(ks):
		for num in numbers:
			if num <= i and ks[i - num] + num > ks[i]:
				ks[i] = ks[i - num] + num
	return ks[-1]
t = int(input())
for _ in range(t):
	(_, k) = [int(el) for el in input().split()]
	nums = [int(el) for el in input().split()]
	print(max_multisum(nums, k))


T = int(input())
for i in range(T):
	(n, k) = map(int, input().split())
	multiset = sorted(list(set([int(x) for x in input().split()])))
	m = len(multiset)
	table = [[0 for i in range(m)] for j in range(k + 1)]
	for i in range(m):
		table[0][i] = 1
	count = [a for a in range(k + 1)]
	for i in range(1, k + 1):
		for j in range(m):
			left = 0
			if i - multiset[j] >= 0:
				left = table[i - multiset[j]][j]
			right = 0
			if j >= 1:
				right = table[i][j - 1]
			table[i][j] = right + left
		if max(table[i]) == 0:
			count.remove(i)
	print(count[-1])


for _ in range(int(input())):
	(n, k) = map(int, input().strip().split())
	numbers = sorted([int(x) for x in input().strip().split()])
	weight = [0] * (k + 1)
	for w in range(1, k + 1):
		maximum = 0
		for number in numbers:
			if number > w:
				break
			elif number + weight[w - number] > maximum:
				maximum = number + weight[w - number]
		weight[w] = maximum
	print(weight[k])


import sys
T = int(sys.stdin.readline())
for x in range(T):
	(n, k) = map(int, sys.stdin.readline().split())
	nset = map(int, sys.stdin.readline().split())
	W = sorted(list(set(nset)))
	m = [0] * (k + 1)
	for i in range(1, k + 1):
		for w in W:
			try:
				val = w + m[i - w]
				if val <= i and val > m[i]:
					m[i] = val
			except IndexError:
				pass
	print(m[-1])


def knapsack(lst, k):
	k_lst = [False for i in range(k + 1)]
	for i in range(len(lst)):
		if lst[i] <= k:
			k_lst[lst[i]] = True
	for i in range(k + 1):
		if k_lst[i]:
			for j in range(len(lst)):
				if i + lst[j] <= k:
					k_lst[i + lst[j]] = True
	if k_lst[k]:
		return k
	else:
		for i in range(k, 0, -1):
			if k_lst[i]:
				return i
		return 0
num_cases = int(input())
for i in range(num_cases):
	string_nums = input().split(' ')
	string_arr = input().split(' ')
	k = int(string_nums[1])
	lst = list(map(int, string_arr))
	print(knapsack(lst, k))


cases = int(input())
for i in range(0, cases):
	(t, target) = map(int, input().split())
	nset = set(map(int, input().split()))
	wset = set()
	nwset = set()
	wset.add(target)
	done = False
	diff = target
	while not done:
		for x in wset:
			for y in nset:
				t = x - y
				if t < diff and t >= 0:
					diff = t
				if t >= 0:
					nwset.add(t)
				if t == 0:
					done = True
					break
		if t == 0:
			wset.add(0)
			break
		if len(nwset) > 0:
			wset = nwset
			nwset = set()
		else:
			done = True
	print(target - diff)


def get_max(sizes, tgt):
	limit = dict()
	for i in range(1, tgt + 1):
		if i in sizes:
			limit[i] = i
			continue
		for size in [x for x in sizes if x < i]:
			lesser_tgt = i - size
			if limit.get(lesser_tgt, 0) + size > limit.get(i, 0):
				limit[i] = limit.get(lesser_tgt, 0) + size
	return limit.get(tgt, 0)
t = int(input().strip())
for i in range(t):
	(n, k) = [int(x) for x in input().strip().split(' ')]
	ip = [int(x) for x in input().strip().split(' ')]
	assert n == len(ip)
	print(get_max(ip, k))


MAXN = 2000
T = int(input())
for t in range(T):
	(n, k) = (int(x) for x in input().split())
	a = [int(x) for x in input().split()]
	dp = [0 for x in range(MAXN + 5)]
	dp[0] = 1
	for i in range(1, k + 1):
		for j in range(n):
			if i - a[j] >= 0 and dp[i - a[j]]:
				dp[i] = 1
				break
	for i in reversed(range(k + 1)):
		if dp[i]:
			print(i)
			break


import functools
import sys
sys.setrecursionlimit(10000)

@functools.lru_cache(maxsize=None)
def max_multiset(numbers, total):
	if not total:
		return 0
	sub_maximums = [0]
	for n in numbers:
		if n <= total:
			sub_maximums.append(n + max_multiset(numbers, total - n))
	return max(sub_maximums)
ncases = int(sys.stdin.readline())
for case_index in range(ncases):
	(size, total) = (int(x) for x in sys.stdin.readline().split())
	numbers = tuple((int(x) for x in sys.stdin.readline().split()))
	assert len(numbers) == size
	print(max_multiset(numbers, total))


T = int(input())
M = []
sol = []
mysol = []
for i in range(0, T):
	del sol[:]
	del mysol[:]
	del M[:]
	lists = [int(i) for i in input().split()]
	N = lists[0]
	for i in range(0, N):
		sol.append(0)
		mysol.append(0)
	capacity = lists[1]
	for i in range(0, capacity + 1):
		M.append(0)
	items = [int(i) for i in input().split()]
	for C in range(1, capacity + 1):
		for i in range(0, N):
			if C >= items[i]:
				sol[i] = M[C - items[i]]
			else:
				sol[i] = 0
		for i in range(0, N):
			if C >= items[i]:
				mysol[i] = sol[i] + items[i]
			else:
				mysol[i] = 0
		M[C] = mysol[0]
		for i in range(1, N):
			if mysol[i] > M[C]:
				M[C] = mysol[i]
	print(M[capacity])


def solve(A, K):
	A = sorted(set(A))
	C = [0] * (K + 1)
	for a in A:
		if a > K:
			break
		for c in range(a, K + 1):
			if C[c] < C[c - a] + a:
				C[c] = C[c - a] + a
	return max(C)
T = int(input())
for _ in range(T):
	(N, K) = (int(_) for _ in input().split())
	A = [int(_) for _ in input().split()]
	print(solve(A, K))


from collections import deque
cases = int(input())
for case in range(cases):
	(numberOfItems, maxWeight) = input().split()
	items = list(set((int(item) for item in input().split())))
	queue = deque()
	queue.append(0)
	seenItems = set()
	seenItems.add(0)
	while len(queue) > 0:
		actual = queue.pop()
		for oper in items:
			if not oper + actual in seenItems and oper + actual <= int(maxWeight):
				queue.append(oper + actual)
				seenItems.add(oper + actual)
	print(max(seenItems))


T = int(input())
for _ in range(T):
	(n, k) = map(int, input().split())
	A = list(map(int, input().split()))
	dp = [False] * (k + 1)
	dp[0] = True
	for a in A:
		for i in range(k - a + 1):
			if dp[i]:
				dp[i + a] = True
	for i in range(k, -1, -1):
		if dp[i]:
			print(i)
			break


import sys
sys.setrecursionlimit(5000)

def take_it(a, j, s):
	s1 = 0
	if j < n - 1:
		s1 = take_it(a, j + 1, s)
	if s + a[j] > k:
		return max(s, s1)
	else:
		s += a[j]
		return max(take_it(a, j, s), s1)
TC = int(input())
for t in range(TC):
	(n, k) = [int(i) for i in input().split(' ')]
	a = [int(i) for i in input().split(' ')]
	print(take_it(a, 0, 0))


def readInput():
	in_array = []
	no_of_test_cases = int(input())
	for i in range(no_of_test_cases):
		target = int(input().split()[1])
		in_array.append((target, set(map(lambda x: int(x), input().split()))))
	return in_array

def solve(test_case):
	expectedSum = test_case[0]
	values = test_case[1]
	solution = [0]
	for i in range(expectedSum + 1):
		if i in values:
			solution.append(i)
		else:
			for j in range(len(solution) - 1, -1, -1):
				if i - solution[j] in values:
					solution.append(i)
					break
	return max(solution)

def run():
	test_cases = readInput()
	for testCase in test_cases:
		print(solve(testCase))
run()


import sys

def main():
	sys.setrecursionlimit(20000)
	T = int(input())
	for i in range(0, T):
		(n, k) = map(int, input().split())
		a = []
		a = list(map(int, input().split()))
		memo = {}
		print(k - getsum(a, k, memo))

def getsum(a, k, memo):
	if k < 0:
		return 2001
	if k == 0 or k - min(a) < 0:
		return k
	if k in memo:
		return memo[k]
	l = []
	for i in a:
		d = getsum(a, k - i, memo)
		l.append(d)
	memo[k] = min(l)
	return min(l)
main()


for _ in range(int(input())):
	(n, k) = [int(i) for i in input().split()]
	xs = [int(i) for i in input().split()]
	m = [0]
	for i in range(1, k + 1):
		m.append(max([m[i - 1]] + [x + m[i - x] for x in xs if i - x >= 0 and x + m[i - x] <= k]))
	print(m[-1])


cases = int(input().strip())
for case in range(0, cases):
	inputs = [int(n) for n in input().strip().split()]
	size = inputs[0]
	Weight = inputs[1]
	weights = [int(n) for n in input().strip().split()]
	if len(weights) == size:
		V = [[None for n in range(0, Weight + 1)] for n in range(0, size + 1)]
		for i in range(0, Weight + 1):
			V[0][i] = 0
		for i in range(1, size + 1):
			V[i][0] = 0
			for W in range(0, Weight + 1):
				if weights[i - 1] <= W:
					if weights[i - 1] + V[i][W - weights[i - 1]] > V[i - 1][W]:
						V[i][W] = weights[i - 1] + V[i][W - weights[i - 1]]
					else:
						V[i][W] = V[i - 1][W]
				else:
					V[i][W] = V[i - 1][W]
	print(V[size][Weight])


t = int(input())
arr = [0] * 2001
while t > 0:
	max = 0
	temp = input().split()
	n = int(temp[0])
	k = int(temp[1])
	knap = [0] * (k + 1)
	temp1 = input().split()
	for i in range(1, n + 1):
		arr[i] = int(temp1[i - 1])
	for i in range(1, k + 1):
		max = knap[i - 1]
		for j in range(1, n + 1):
			if arr[j] <= i:
				val = arr[j] + knap[i - arr[j]]
			else:
				val = 0
			if val >= max:
				max = val
		knap[i] = max
	print(knap[k])
	t -= 1


def f(l, n, k):
	l.sort()
	dp = []
	for i in range(k + 1):
		if i in l:
			dp.append(True)
		else:
			dp.append(False)
	for i in range(k + 1):
		if dp[i] == False:
			for j in range(n):
				if i - l[j] < 0:
					break
				if dp[i - l[j]] == True:
					dp[i] = True
	for i in range(k, 0, -1):
		if dp[i]:
			return i
	return 0
t = int(input())
for _ in range(t):
	(n, k) = [int(v) for v in input().split()]
	l = [int(v) for v in input().split()]
	print(f(l, n, k))


import sys
nb_tests = int(sys.stdin.readline())

def come_close(array, k):
	maxes = {0: 0}
	for i in range(1, k + 1):
		maxes[i] = 0
		for j in array:
			if i < j:
				continue
			maxes[i] = max(maxes[i], maxes[i - j] + j)
	return maxes[k]
for test_index in range(nb_tests):
	(n, k) = tuple([int(i) for i in sys.stdin.readline().split(' ')])
	array = [int(i) for i in sys.stdin.readline().split(' ')]
	print(come_close(array, k))


def knapsack(N, W, items):
	d = [0]
	for c in range(1, W + 1):
		d.append(d[c - 1])
		for i in range(N):
			if items[i] <= c:
				d[c] = max(d[c], d[c - items[i]] + items[i])
	return d[c]
cases = int(input())
for case in range(cases):
	(N, W) = map(int, input().split())
	items = list(map(int, input().split()))
	print(knapsack(N, W, items))


T = int(input())
for _ in range(T):
	(n, k) = [int(x) for x in input().split()]
	A = [int(x) for x in input().split()]
	A.sort()
	count = [None for _ in range(k + 1)]
	count[0] = 0
	for i in range(1, k + 1):
		for a in A:
			if a > i:
				break
			elif count[i - a] is not None:
				count[i] = i
				break
	for i in range(k + 1)[::-1]:
		if count[i] is not None:
			print(i)
			break


T = int(input())
for tc in range(T):
	tt = input().split()
	n = int(tt[0])
	k = int(tt[1])
	a = []
	for r in input().split():
		a.append(int(r))
	b = {}
	for i in range(k + 1):
		b[i] = False
	b[0] = True
	for c in a:
		for i in range(k + 1):
			if b[i]:
				if i + c <= k:
					b[i + c] = True
	for i in range(k, -1, -1):
		if b[i]:
			print(i)
			break


import bisect
for i in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	A = [int(x) for x in input().split()]
	A = list(set(A))
	A.sort()
	t = []
	for i in range(1, k + 1):
		s = 0
		if i >= A[0]:
			idx = bisect.bisect_left(A, i)
			if idx < len(A) and A[idx] == i:
				s = i
			else:
				for j in range(idx):
					s = max(s, A[j], t[i - A[j] - 1])
					if s == i:
						break
					c = A[j] + t[i - A[j] - 1]
					if c > s and c <= i:
						s = c
		t.append(s)
	print(t[k - 1])


def knap(esumm, summy, csum=0):
	global maxsum
	if csum == esum:
		maxsum = [csum]
	elif csum < esumm:
		for elem in summy:
			csum1 = csum + elem
			if csum1 <= esumm:
				maxsum.append(csum1)
			knap(esumm, summy, csum1)
tcase = int(input())
for tcases in range(tcase):
	maxsum = []
	(alen, esum) = map(int, input().rsplit())
	sumy = list(map(int, input().rsplit()))
	flagdiv = 0
	for elems in sumy:
		if esum % elems == 0:
			flagdiv = 1
	if flagdiv == 0:
		knap(esum, sumy)
		if len(maxsum) == 0:
			print(0)
		else:
			print(max(maxsum))
	else:
		print(esum)


T = int(input())
for _ in range(T):
	(n, k) = [int(i) for i in input().split()]
	a = [int(i) for i in input().split()]
	sums = [[0 for _ in range(k + 1)] for _ in range(n)]
	for i in range(n):
		for c in range(1, k + 1):
			sum1 = 0 if i == 0 else sums[i - 1][c]
			sum2 = 0 if a[i] > c else a[i] + sums[i][c - a[i]]
			sums[i][c] = max(sum1, sum2)
	print(sums[-1][-1])


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	A = sorted(map(int, input().split()))
	nearPossibleSum = [0 for i in range(K + 1)]
	for a in A:
		for i in range(K + 1):
			if i >= a:
				nearPossibleSum[i] = max(nearPossibleSum[i], nearPossibleSum[i - a] + a)
	print(nearPossibleSum[K])


from itertools import combinations

def knapsack(array, expected):
	if 1 in array:
		return expected
	m = [0 for i in range(expected + 1)]
	for i in range(expected + 1):
		m[i] = m[i - 1]
		for (k, vk) in enumerate(array):
			if array[k] <= i and m[i] < m[i - array[k]] + vk:
				m[i] = m[i - array[k]] + vk
	return m[expected]
line1 = input()
try:
	while True:
		(num_item, expected) = list(map(int, input().split()))
		array = list(map(int, input().split()))
		print(knapsack(array, expected))
except:
	pass


import sys
__author__ = 'nutic'

def knapsack(arr, expected):
	f = [[0 for _ in range(0, expected + 1)] for _ in arr]
	for (k, _) in enumerate(arr):
		for n in range(0, expected + 1):
			if k == 0:
				if arr[k] > n:
					f[k][n] = n
				else:
					f[k][n] = min(n, f[k][n - arr[k]])
			elif arr[k] > n:
				f[k][n] = f[k - 1][n]
			else:
				f[k][n] = min(f[k - 1][n], f[k][n - arr[k]])
	return expected - f[len(arr) - 1][expected]
lines = sys.stdin.read().split('\n')
lines = iter(lines)
t = int(next(lines))

def read_line_of_numbers(line: str, number_type=int):
	return list(map(number_type, line.split(' ')))
for i in range(0, t):
	(k, expected, *_) = read_line_of_numbers(next(lines))
	ar = read_line_of_numbers(next(lines))
	sys.stdout.write(str(knapsack(ar, expected)))
	sys.stdout.write('\n')


t = int(input())
while t > 0:
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	a = n * [0]
	a = input().split()
	a = [int(i) for i in a]
	b = (k + 1) * [0]
	done = 0
	for i in range(0, n):
		if a[i] == k:
			print(k)
			done = 1
			break
		elif a[i] > k:
			continue
		else:
			b[a[i]] = 1
	if done == 0:
		for i in range(1, k + 1):
			if b[i] == 1:
				for j in range(0, n):
					if i + a[j] == k:
						print(k)
						done = 1
						break
					elif i + a[j] > k:
						continue
					else:
						b[i + a[j]] = 1
				if done == 1:
					break
	if done == 0:
		tmp = k
		while tmp > 0:
			if b[tmp] == 1:
				print(tmp)
				done = 1
				break
			tmp -= 1
	if done == 0:
		print('0')
	t -= 1


def knapsack(arr, s):
	result = 0
	for n in arr:
		if n <= s and n > result:
			result = n
	if result != 0:
		nums = [True]
		for i in range(1, s + 1):
			nums.append(False)
			for n in arr:
				goal = i - n
				if goal >= 0 and goal < i and nums[goal]:
					nums[i] = True
					result = i
	return result
for i in range(0, int(input())):
	(n, k) = input().split()
	k = int(k)
	nums = [int(n) for n in input().split()]
	print(knapsack(nums, k))


from collections import defaultdict

def solve():
	capacity = int(input().split()[1])
	weights = set([int(val) for val in input().split()])
	capacities = defaultdict(lambda : 0)
	for i in range(1, capacity + 1):
		possibilities = [capacities[i - 1]] + [capacities[i - w] + w for w in weights]
		possibilities = [c for c in possibilities if c <= i]
		capacities[i] = max(possibilities)
	print(capacities[capacity])
T = int(input())
while T > 0:
	solve()
	T = T - 1


T = int(input())
for _ in range(T):
	(n, k) = input().split()
	(n, k) = (int(n), int(k))
	a = input().split()
	a = sorted([int(ai) for ai in a])
	M = [0] * (k + 1)
	M[0] = 1
	best_so_far = 0
	for x in range(1, k + 1):
		for aj in a:
			if x - aj < 0:
				break
			elif M[x - aj] == 1:
				M[x] = 1
				best_so_far = x
				break
	print(best_so_far)


import sys

def dynamic(ary, s):
	m = min(ary)
	a = []
	for i in range(m):
		a.append(0)
	a.append(m)
	for i in range(m + 1, s + 1, 1):
		ma = 0
		for j in ary:
			if i >= j and a[i - j] + j > ma:
				ma = a[i - j] + j
		a.append(max(a[i - 1], ma))
	return a[s]

def findSum(ary, s):
	l = len(ary)
	div = [s // x for x in ary]
	red = [s % x for x in ary]
	if 0 in red:
		return s
	else:
		return dynamic(ary, s)
data = sys.stdin.readlines()
cases = int(data[0])
for i in range(cases):
	line1 = data[1 + 2 * i]
	n = line1.split()
	s = int(n[1])
	line2 = data[2 + 2 * i]
	ary = list(map(int, line2.split()))
	ans = findSum(ary, s)
	print(ans)


T = int(input())
for t in range(T):
	(n, W) = map(int, input().split())
	V = set(map(int, input().split()))
	m = [0]
	for w in range(1, W + 1):
		try:
			m.append(max((v + m[w - v] for v in V if w - v >= 0)))
		except ValueError:
			m.append(0)
	print(m[W])


T = int(input())
for _ in range(0, T):
	(n, k) = map(int, input().strip().split())
	arr = [int(i) for i in input().strip().split()]
	wset = set()
	for i in range(0, n):
		wset.add(arr[i])
	dp = set()
	dp.add(0)
	c_min = min(arr)
	curr_ret = 0
	while c_min <= k:
		nset = set()
		for wv in wset:
			for dv in dp:
				nv = wv + dv
				if nv <= k and nv not in nset:
					nset.add(nv)
					if k - curr_ret > k - nv and k - nv >= 0:
						curr_ret = nv
		if len(nset) > 0:
			c_min = min(nset)
			dp = nset
		else:
			break
	print(curr_ret)


for t in range(int(input())):
	(n, k) = [int(i) for i in input().split()]
	a = list(map(int, input().split()))
	stack = [(k, 0)]
	m = k
	while stack:
		(r, i) = stack.pop()
		if i == n:
			m = min(m, r)
		else:
			ai = a[i]
			for l in range(r // ai + 1):
				stack.append((r - l * a[i], i + 1))
	print(k - m)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	mem = [[0 for _ in range(k + 1)] for _ in range(n + 1)]
	a = [int(x) for x in input().split()]
	for i in range(1, n + 1):
		for j in range(1, k + 1):
			if a[i - 1] <= j:
				mem[i][j] = max(mem[i - 1][j - a[i - 1]] + a[i - 1], mem[i][j - a[i - 1]] + a[i - 1], mem[i - 1][j])
			else:
				mem[i][j] = max(mem[i][j - 1], mem[i - 1][j])
	print(mem[-1][-1])


import sys
test_num = int(sys.stdin.readline().strip())
for _ in range(test_num):
	expected = int(sys.stdin.readline().strip().split()[1])
	num = set([int(s) for s in sys.stdin.readline().strip().split()])
	dp = [False for i in range(expected + 1)]
	dp[0] = True
	result = 0
	for i in range(1, len(dp)):
		for n in num:
			if i >= n and dp[i - n]:
				dp[i] = True
				result = i
				break
	print(result)


def solve(item_list, k):
	look_up = {0}
	for i in range(1, k + 1):
		for j in item_list:
			if j <= i and i - j in look_up:
				look_up.add(i)
	return max(look_up)
for i in range(int(input())):
	(n, k) = [int(i) for i in input().split()]
	item_list = [int(i) for i in input().split()]
	print(solve(item_list, k))


from sys import setrecursionlimit
setrecursionlimit(2500)
cache = []

def main():
	ncases = int(input())
	for _ in range(ncases):
		(npieces, cap) = readints()
		pieces = readints()
		assert npieces == len(pieces)
		pieces = sorted(set(pieces))
		cache[:] = [0] + [None] * cap
		print(bestfit(pieces, cap))

def readints():
	return [int(f) for f in input().split()]

def bestfit(pieces, cap):
	if cache[cap] is not None:
		return cache[cap]
	best = 0
	for piece in pieces:
		if piece > cap:
			break
		best = max(best, piece + bestfit(pieces, cap - piece))
		if best == cap:
			break
	cache[cap] = best
	return best
main()


def main():
	import sys
	sys.setrecursionlimit(100000000)

	def solve(x, k):
		if x >= n:
			return 0
		if k <= 0:
			return 0
		if dp[x][k] != -1:
			return dp[x][k]
		dp[x][k] = 0
		for i in range(k // A[x] + 1):
			dp[x][k] = max(dp[x][k], i * A[x] + solve(x + 1, k - A[x] * i))
		return dp[x][k]
	for T in range(int(input())):
		(n, K) = map(int, input().split())
		A = list(set([int(x) for x in input().split()]))
		n = len(A)
		dp = [[-1 for k in range(K + 1)] for x in range(n)]
		print(solve(0, K))
main()


T = int(input())
for case in range(T):
	(N, K) = map(int, input().rstrip().split(' '))
	A = list(map(int, input().rstrip().split(' ')))
	dp = [False] * (K + 1)
	dp[0] = True
	for c in A:
		for i in range(c, len(dp)):
			dp[i] |= dp[i - c]
	print(max((i for i in range(len(dp)) if dp[i])))


def unbounded_knapsack(W, w):
	m = [0 for i in range(W + 1)]
	start = min(w)
	for i in range(start, W + 1):
		m[i] = m[i - 1]
		for (k, vk) in enumerate(w):
			if w[k] <= i and m[i] < m[i - w[k]] + vk:
				m[i] = m[i - w[k]] + vk
	return m[W]
t = int(input())
for i in range(t):
	inp = input().split()
	[n, k] = [int(x) for x in inp]
	inp = input().split()
	arr = [int(x) for x in inp]
	print(unbounded_knapsack(k, arr))


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = sorted([int(x) for x in input().split()])
	cnt = [0] * 2005
	cnt[0] = 1
	for c in arr:
		for i in range(c, k + 1):
			cnt[i] += cnt[i - c]
	ans = 0
	for i in range(k, -1, -1):
		if not cnt[i] == 0:
			ans = i
			break
	print(ans)


T = int(input())

def findBestResult(A, k):
	tsumdict = dict()
	for x in A:
		tsumdict[x] = 0
	for i in range(1, k + 1):
		if i < A[0]:
			tsumdict[i] = i
		elif i in tsumdict:
			continue
		else:
			tsumdict[i] = min([tsumdict[j] + tsumdict[i - j] for j in range(1, i // 2 + 1)])
	return k - tsumdict[k]
for i in range(T):
	(n, k) = [int(s) for s in input().split()]
	A = [int(s) for s in input().split()]
	A = list(set(A))
	A.sort()
	print(str(findBestResult(A, k)))


def knapsack2(count, total, items):
	selected_sum = [0] * (total + 1)
	selected_items = [[]] * (total + 1)
	for i in range(count):
		for total_part in range(items[i], total + 1):
			new_sum = selected_sum[total_part - items[i]] + items[i]
			if new_sum > selected_sum[total_part] and new_sum <= total:
				selected_sum[total_part] = new_sum
				selected_items[total_part] = selected_items[total_part - items[i]] + [items[i]]
	return (selected_sum, selected_items)
cases = int(input())
results = []
for case in range(cases):
	line1 = input().split()
	line2 = input().split()
	n = int(line1[0])
	k = int(line1[1])
	A = [int(x) for x in line2]
	(sums, items) = knapsack2(n, k, A)
	results.append(sums[-1])
for result in results:
	print(result)


T = int(input())
while T != 0:
	T = T - 1
	lst = []
	data = input().split()
	[num, size] = [int(data[0]), int(data[1])]
	data = input().split()
	for i in range(num):
		lst.append(int(data[i]))
	A = [0 for x in range(size + 1)]
	for j in range(size + 1):
		A[j] = 0
	for i in range(1, size + 1):
		for j in range(num):
			if lst[j] <= i:
				A[i] = max(A[i], A[i - lst[j]] + lst[j])
	print(A[size])


def knapsack(items, n, w):
	items.sort()
	dp = [0] * (w + 1)
	for i in range(1, n + 1):
		wi = items[i - 1]
		for j in range(wi, w + 1):
			if wi <= j:
				dp[j] = max(dp[j], dp[j - wi] + wi)
	return dp[w]
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	print(knapsack(a, n, k))


t = int(input())
for i in range(0, t):
	(n, k) = [int(x) for x in input().split()]
	A = [int(x) for x in input().split()]
	p = []
	p.append(0)
	for a in range(1, k + 1):
		l = []
		for v in range(0, n):
			if A[v] <= a:
				l.append(p[a - A[v]] + A[v])
		if not l:
			p.append(0)
		else:
			p.append(max(l))
	print(p[k])


def unbounded_knapsack(L, k):
	L.sort()
	dp = [0] * (k + 1)
	for i in L:
		if i > k:
			break
		for j in range(i, k + 1):
			if dp[j] < dp[j - i] + i:
				dp[j] = dp[j - i] + i
	return dp[k]
numTrials = int(input())
for i in range(numTrials):
	(n, k) = map(int, input().split())
	L = list(map(int, input().split()))
	print(unbounded_knapsack(L, k))


import sys

def get_unused_space(a, space, cache):
	if space == 0:
		return 0
	if space in cache:
		return cache[space]
	spaces = []
	for ai in a:
		if space - ai >= 0:
			s = get_unused_space(a, space - ai, cache)
			spaces.append(s)
	result = min(spaces) if spaces else space
	cache[space] = result
	return result

def main():
	t = int(sys.stdin.readline())
	for k in range(t):
		(_, expected_sum) = map(int, sys.stdin.readline().split())
		a = list(map(int, sys.stdin.readline().split()))
		cache = {}
		print(expected_sum - get_unused_space(a, expected_sum, cache))
sys.setrecursionlimit(10000)
main()


T = int(input())
for t in range(T):
	(n, k) = map(int, input().split())
	nums = map(int, input().split())
	sums = [True] + [False] * k
	for num in nums:
		for i in range(len(sums) - num):
			sums[i + num] = sums[i + num] or sums[i]
	i = k
	while i >= 0 and (not sums[i]):
		i -= 1
	print(i)


def knapsack(items, desired_weight):
	max_value = {0: 0}
	for w in range(1, desired_weight + 1):
		options = [item[0] + max_value[w - item[1]] for item in filter(lambda x: x[1] <= w, items)]
		max_value[w] = max(options) if options else 0
	return max_value[desired_weight]
for n in range(int(input())):
	(_, desired_weight) = list(map(int, input().split()))
	sequence = list(map(int, input().split()))
	print(knapsack([(i, i) for i in sequence], desired_weight))


caseNum = int(input())
for case in range(0, caseNum):
	(n, k) = list(map(int, input().split()))
	a = set(map(int, input().split()))
	la = len(a)
	lla = list(a)
	lla.sort()
	memo = [-1 for x in range(k + 1)]
	for i in range(0, k // lla[0] + 1):
		memo[i * lla[0]] = i * lla[0]
	for t in range(1, la):
		for i in range(k // lla[t] + 1):
			for j in range(k + 1 - i * lla[t]):
				if memo[j] >= 0:
					memo[j + i * lla[t]] = j + i * lla[t]
	print(max(max(memo), 0))


__author__ = 'Shivani'
import sys

def knapsack(knap, l):
	stack = [0]
	rec = [0] * (knap + 1)
	m = 0
	while stack:
		a = stack.pop(0)
		for i in l:
			r = i + a
			if r < knap and rec[r] == 0:
				stack.append(r)
				rec[r] = 1
				if r > m and r <= knap:
					m = r
			elif r == knap:
				m = r
				break
		if m == knap:
			break
	print(m)

def main():
	for i in range(int(input())):
		(n, knap) = input().split()
		(n, knap) = (int(n), int(knap))
		l = list(map(int, input().split()))
		knapsack(knap, l)
main()


t = eval(input())

def max(a, b):
	return a if a > b else b
while t > 0:
	t -= 1
	(n, k) = map(int, input().split())
	arr = list(set(map(int, input().split())))
	n = len(arr)
	mat = [[0] * (k + 1) for i in range(n)]
	for i in range(n):
		for j in range(k + 1):
			temp1 = 0
			temp2 = 0
			if j >= arr[i]:
				temp1 = arr[i] + mat[i][j - arr[i]]
			if i >= 1:
				temp2 = mat[i - 1][j]
			mat[i][j] = max(temp1, temp2)
	print(mat[n - 1][k])


import sys
sys.setrecursionlimit(10000)

def run():
	(n, k) = list(map(int, input().strip().split(' ')))
	nums = list(map(int, input().strip().split(' ')))

	def cache(fn):
		data = {}

		def newFn(*args):
			h = hash(tuple(args))
			if h in data:
				return data[h]
			else:
				rtn = fn(*args)
				data[h] = rtn
				return rtn
		return newFn

	@cache
	def find(i, k):
		if i == -1 or k <= 0:
			return 0
		a = nums[i] + find(i, k - nums[i])
		b = find(i - 1, k)
		s = 0
		if k - a >= 0:
			s = max(s, a)
		if k - b >= 0:
			s = max(s, b)
		return s
	print(find(n - 1, k))
for i in range(int(input())):
	run()


cases = int(input())
for i in range(cases):
	(length, target) = input().split()
	target = int(target)
	bag = list(set([int(y) for y in input().split()]))
	bag.sort()
	table = [[0] * (target + 1) for _ in range(target + 1)]
	for y in range(0, target + 1):
		for x in bag:
			if x > y:
				break
			diff = y - x
			if table[y][y] == 0:
				table[y][y] = max(table[diff][diff] + x, table[y - 1][y - 1])
			else:
				temp = max(table[diff][diff] + x, table[y - 1][y - 1])
				table[y][y] = max(temp, table[y][y])
	print(table[target][target])


def solve(a, k):
	arr = [0] * (k + 1)
	for t in a:
		for x in range(t, k + 1):
			arr[x] = max(arr[x], arr[x - t] + t)
	return arr[k]
t = int(input())
for x in range(t):
	m = [int(l) for l in input().split()]
	print(solve([int(l) for l in input().split()], m[1]))


for i in range(int(input())):
	(x, y) = map(int, input().split(' '))
	l = list(map(int, input().split(' ')))
	initx = 0
	dp = [0] * 2005
	dp[0] = 1
	for i in range(y + 1):
		init = False
		for j in l:
			if i - j >= 0:
				if dp[i - j] == 1:
					init = True
		if init == True:
			dp[i] = True
			initx = i
	print(initx)


def solve(n, k):
	memo = [0 for _ in range(k + 1)]
	for weight in range(1, k + 1):
		for item in n:
			if item <= weight:
				memo[weight] = max(memo[weight], memo[weight - item] + item)
	return memo[k]
for testcase in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	knapsack = [int(x) for x in input().split()]
	print(solve(knapsack, k))


def knapExp(A, s):
	M = [0 for k in range(s + 1)]
	for k in range(1, s + 1):
		for j in range(len(A)):
			if A[j] <= k:
				M[k] = max(M[k], M[k - A[j]] + A[j])
	print(M[s])
T = int(input())
for i in range(T):
	(n, k) = input().split()
	A = input().split()
	a = [0 for k in range(int(n))]
	for j in range(int(n)):
		a[j] = int(A[j])
	knapExp(a, int(k))


def knapsack(N, K, A):
	B = [0 for _ in range(K + 1)]
	M = min(A)
	for i in range(M, K + 1):
		B[i] = B[i - 1]
		for j in range(N):
			if A[j] <= i:
				B[i] = max(B[i], B[i - A[j]] + A[j])
	return B[K]

def main():
	T = int(input())
	for _ in range(T):
		(N, K) = [int(i) for i in input().split()]
		A = [int(i) for i in input().split()]
		print(knapsack(N, K, A))
main()


import functools
functools.lru_cache()
import sys
sys.setrecursionlimit(2500)

def knap(A, T, i):
	if i < 0:
		return 0
	if A[i] > T:
		return knap(A, T, i - 1)
	else:
		return max(knap(A, T, i - 1), knap(A, T - A[i], i) + A[i])
t = int(input())
a = 0
while a < t:
	a += 1
	info = list(map(int, input().split()))
	array = list(map(int, input().split()))
	ans = knap(array, info[1], len(array) - 1)
	print(ans)


for tests in range(int(input())):
	[n, k] = [int(i) for i in input().split()]
	A = [int(i) for i in input().split()]
	M = [0]
	for i in range(1, k + 1):
		B = [0]
		for j in A:
			if j <= i:
				B.append(j + M[i - j])
		M.append(max(B))
	print(M[k])


import sys

def minCoinsForSum(s, values):
	minList = []
	minList.append(0)
	minSum = 0
	for i in range(1, s + 1):
		minList.append(float('inf'))
		for j in range(len(values)):
			if values[j] <= i and minList[i] >= 1 + minList[i - values[j]]:
				minList[i] = 1 + minList[i - values[j]]
				if minList[i] != float('inf'):
					minSum = i
	return minSum
num_test_cases = input()
for i in range(int(num_test_cases)):
	line = input()
	(n, k) = [int(i) for i in line.strip().split()]
	line = input()
	values = [int(i) for i in line.strip().split()]
	print(minCoinsForSum(k, values))


def read_tuple():
	return [int(s) for s in input().split()]

def print_matrix(matrix, columns):
	print(' '.join([' ', ' '] + [str(x) for x in columns]))
	for (i, row) in enumerate(matrix):
		print(' '.join([str(i)] + [str(int(x)) for x in row]))

def knapsack(capacity, weights):
	m = capacity + 1
	n = len(weights) + 1
	matrix = [[0 for _ in range(n)] for _ in range(m)]
	for i in range(1, m):
		for j in range(1, n):
			weight = weights[j - 1]
			not_using_weight = matrix[i][j - 1]
			using_weight = matrix[i - weight][j] + weight if i >= weight else 0
			matrix[i][j] = max(not_using_weight, using_weight)
	return matrix[-1][-1]
for _ in range(int(input())):
	print(knapsack(read_tuple()[1], read_tuple()))


import sys
sys.setrecursionlimit(10000)

def memoize(function):
	cache = dict()

	def memoized_function(*args):
		if args in cache:
			return cache[args]
		else:
			result = function(*args)
			cache[args] = result
			return result
	return memoized_function

@memoize
def solve(n, A):
	if n == 0:
		return n
	current_soln = n
	for a in A:
		if n >= a:
			current_soln = min(current_soln, solve(n - a, A))
	return current_soln
T = int(sys.stdin.readline())
for case in range(T):
	[_n, k] = [int(X) for X in sys.stdin.readline().split()]
	A = frozenset([int(X) for X in sys.stdin.readline().split()])
	print(k - solve(k, A))


tc = int(input())
for t in range(tc):
	(_, k) = (int(x) for x in input().split())
	A = sorted(list(set([int(x) for x in input().split()])))
	num_items = len(A)
	dp = list()
	for i in range(num_items + 1):
		dp.append([0] * (k + 1))
	for it in range(1, len(dp)):
		for j in range(1, len(dp[0])):
			if j - A[it - 1] >= 0:
				dp[it][j] = max(dp[it - 1][j], A[it - 1] + dp[it][j - A[it - 1]])
			else:
				dp[it][j] = dp[it - 1][j]
	print(dp[-1][-1])


test_cases = int(input().strip())
for test_case in range(test_cases):
	(n, capacity) = [int(item) for item in input().strip().split()]
	values = set([int(item) for item in input().strip().split()])
	dp_arr = [True]
	while len(dp_arr) <= capacity:
		reachable = False
		for value in values:
			if value <= len(dp_arr) and dp_arr[-value]:
				reachable = True
				break
		dp_arr.append(reachable)
	for (idx, is_reachable) in enumerate(reversed(dp_arr)):
		if is_reachable:
			print(capacity - idx)
			break


T = int(input())
for t in range(0, T):
	var = input().split()
	(n, k) = (int(var[0]), int(var[1]))
	arr = [False] * (k + 1)
	var = input().split()
	found = False
	changed_flag = True
	arr[0] = True
	for i in range(0, n):
		num = int(var[i])
		if num <= k:
			arr[num] = True
			if num == k:
				found = True
	while found == False and changed_flag == True:
		changed_flag = False
		for i in range(1, k + 1):
			if arr[i] == False:
				continue
			for j in range(1, k + 1 - i):
				if arr[j] == False:
					continue
				if arr[i + j] == False:
					arr[i + j] = True
					changed_flag = True
		if changed_flag == False:
			break
	for i in range(k, -1, -1):
		if arr[i] == True:
			print(i)
			break


def f(array, k):
	cache = [i for i in range(k + 1)]
	for i in range(1, k + 1):
		for j in array:
			if j <= i:
				cache[i] = min(cache[i], cache[i - j])
	return cache[k]
for i in range(int(input())):
	(n, k) = [int(i) for i in input().split()]
	print(k - f([int(i) for i in input().split()], k))


import sys
sys.setrecursionlimit(1000000)
t = int(input())
for i in range(t):
	(x, mK) = map(int, input().split())
	n = list(map(int, input().split()))
	mDp = [(mK + 1) * [-1] for i in range(x)]

	def make(k, ind):
		if k <= 0 or ind < 0:
			return 0
		if mDp[ind][k] > -1:
			return mDp[ind][k]
		mDp[ind][k] = make(k, ind - 1)
		if n[ind] <= k:
			mDp[ind][k] = max(mDp[ind][k], n[ind] + make(k - n[ind], ind))
		return mDp[ind][k]
	print(make(mK, x - 1))


import sys
sys.setrecursionlimit(10000)

def do_stuff(k, l):
	explored = set()

	def get_max(x):
		for i in l:
			if x + i not in explored and x + i <= k:
				explored.add(x + i)
				yield max(get_max(x + i))
		yield x
	print(max(get_max(0)))
t = int(input())
for i in range(t):
	(n, k) = [int(x) for x in input().split()]
	l = [int(x) for x in input().split()]
	do_stuff(k, l)


def knapsack(k, a, M):
	if k == 0 or len(a) == 0:
		return k
	if k in M:
		return M[k]
	R = [k]
	for x in a:
		if x > k:
			continue
		if k % x == 0:
			R.append(0)
		else:
			R.append(knapsack(k - x, a, M))
	M[k] = min(R)
	return M[k]
T = int(input())
for _ in range(T):
	l = input().split()
	K = int(l[1])
	A = list(map(int, input().split()))
	print(K - knapsack(K, A, {}))


def solve(sz_arr, max_sum, arr):
	t = [[0 for _ in range(max_sum + 1)] for _ in range(sz_arr + 1)]
	for i in range(sz_arr + 1):
		for j in range(max_sum + 1):
			t[i][j] = t[i - 1][j]
			if j >= arr[i - 1]:
				t[i][j] = max(t[i - 1][j], arr[i - 1] + t[i - 1][j - arr[i - 1]], arr[i - 1] + t[i][j - arr[i - 1]])
	return t[sz_arr][max_sum]
for _ in range(int(input())):
	(sz_arr, max_sum) = list(map(int, input().split()))
	print(solve(sz_arr, max_sum, list(map(int, input().split()))))


from collections import deque

def get_sum(values, k):
	values = sorted(values)
	can_create = set([0])
	q = deque([0])
	while q:
		i = q.pop()
		if i > 10 * k:
			break
		for val in values:
			s = i + val
			if s not in can_create:
				can_create.add(s)
				q.appendleft(s)
	for i in range(k, 0, -1):
		if i in can_create:
			return i
	return 0
T = int(input())
for t in range(T):
	(n, k) = list(map(int, input().split()))
	values = list(map(int, input().split()))
	print(get_sum(values, k))


def knapsack(weights, total):
	assert all((weight > 0 for weight in weights))
	sums = []
	sums.append(0)
	for _ in range(1, total + 1):
		best = 0
		for weight in weights:
			if len(sums) - weight >= 0:
				best = max(best, weight + sums[-weight])
		sums.append(best)
	assert len(sums) == total + 1
	return sums[-1]
numtests = int(input())
for _ in range(numtests):
	[_, total] = [int(s) for s in input().split()]
	weights = [int(s) for s in input().split()]
	print(knapsack(weights, total))


def knapsack(a, n, k):
	dp = [0] * (k + 1)
	for i in range(1, k + 1):
		for j in range(0, n):
			if a[j] <= i:
				dp[i] = max(dp[i], dp[i - a[j]] + a[j])
	print(dp[k])

def main():
	T = int(input())
	for i in range(0, T):
		(n, k) = [int(i) for i in input().split(' ')]
		a = list(map(int, input().split(' ')))
		knapsack(a, n, k)
main()


def knapsack(array, n, sum_):
	table = [0] * (sum_ + 1)
	table[0] = 1
	for i in range(n):
		for j in range(array[i], sum_ + 1):
			table[j] += table[j - array[i]]
	max_ = -1
	a = 0
	for i in range(sum_, 0, -1):
		if table[i] >= 1:
			a = i
			break
	return a
n_tests = int(input())
for i in range(n_tests):
	(n, sum_) = [int(x) for x in input().split()]
	array = [int(x) for x in input().split()]
	answer = knapsack(array, n, sum_)
	print(answer)


def calculate_knapsack(max_weight, values):
	matrix = [[0 for i in range(max_weight + 1)] for j in range(len(values) + 1)]
	for (n, value) in enumerate(values):
		for i in range(max_weight + 1):
			if value > i:
				matrix[n + 1][i] = matrix[n][i]
			else:
				a = matrix[n][i]
				j = int(i / value)
				c = 0
				for k in range(1, j + 1):
					b = matrix[n][i - k * value] + k * value
					if b > c:
						c = b
					matrix[n + 1][i] = max(a, c)
	return matrix[len(values)][max_weight]
t = int(input())
for i in range(t):
	(n, max_weight) = [int(x) for x in input().split()]
	values = [int(k) for k in input().split()]
	max_weight_possible = calculate_knapsack(max_weight, values)
	print(max_weight_possible)


from sys import stdin
import dis
get = iter(map(int, stdin.read().split())).__next__

def knapSack(lis, K, N):
	dp = [[0] * (K + 1)] * (N + 1)
	for n in range(N + 1):
		for k in range(K + 1):
			if k == 0:
				dp[n][k] = 0
			elif n == 0:
				dp[n][k] = 0
			elif k >= lis[n - 1]:
				dp[n][k] = max(lis[n - 1] + dp[n][k - lis[n - 1]], dp[n - 1][k])
			else:
				dp[n][k] = dp[n - 1][k]
	return dp[N][K]

def main():
	t = get()
	for _ in range(t):
		n = get()
		k = get()
		lis = []
		for _ in range(n):
			lis.append(get())
		print(knapSack(lis, k, n))
main()