Read problems statements in Russian also. 
Chef likes shopping, and especially he likes to buy oranges. But right now he is short of money. He has only k rubles. There are n oranges. The i-th one costs cost_{i} rubles and has weight equal to weight_{i}. Chef wants to buy a set of oranges with the maximal possible weight. Please help him, and tell him this weight.

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

The first line of the input contains an integer T  denoting the number of test cases. The first line of each test case contains two numbers n and k. The following n lines contain two numbers cost_{i} and weight_{i} respectively. 

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

For each test case, output a single line containing maximal weight among all the affordable sets of oranges. 

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

$1 ≤ T ≤  250 $
$1 ≤ n ≤  10 $
$1 ≤ k ≤  100000000 $
$1 ≤ weight_{i} ≤  100000000 $
$1 ≤ cost_{i} ≤  100000000 $

------ Scoring ------ 

Subtask 1 (30 points): All the oranges' weights equals to 1.

Subtask 2 (30 points):   N = 5  

Subtask 2 (40 points):  See the constraints 

----- Sample Input 1 ------ 
2
1 3
2 2
3 4
2 1
2 2
3 5
----- Sample Output 1 ------ 
2
5

Difficulty: MEDIUM_HARD
Tags: Bit manipulation

Mathematics

Complete search
Skill types: Bit manipulation

Complete search

Starter code:

Solutions:
from itertools import combinations
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = []
	b = []
	c = list(range(n))
	for _ in range(n):
		(d, e) = map(int, input().split())
		a.append(d)
		b.append(e)
	ans = 0
	for r in range(1, n + 1):
		x = combinations(c, r)
		for i in x:
			cost = 0
			weight = 0
			for j in i:
				cost += a[j]
				weight += b[j]
			if cost <= k and weight > ans:
				ans = weight
	print(ans)


def mainstuff(k, cost, weight):
	global a
	m = -1
	for i in range(2 ** len(cost)):
		t = list(map(int, list(str(format(i, '0' + str(n) + 'b')))))
		t1 = sum([a * b for (a, b) in zip(cost, t)])
		t2 = sum([a * b for (a, b) in zip(weight, t)])
		if t1 <= k:
			if t2 > m:
				m = t2
	print(m)
t = int(input())
for a0 in range(t):
	(n, k) = map(int, input().strip().split(' '))
	cost = []
	weight = []
	t = {}
	for a1 in range(n):
		(t1, t2) = map(int, input().strip().split(' '))
		cost.append(t1)
		weight.append(t2)
	mainstuff(k, cost, weight)


def solve(C, W, K):
	n = len(C)
	max_ = 0
	for i in range(1 << n):
		weight = 0
		ans = []
		k = K
		for j in range(n):
			if i & 1 << j:
				ans.append(W[j])
				if C[j] <= k:
					k -= C[j]
					weight += W[j]
		max_ = max(max_, weight)
	return max_
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	C = []
	W = []
	for i in range(n):
		(c, w) = map(int, input().split())
		C.append(c)
		W.append(w)
	print(solve(C, W, k))


from itertools import combinations
try:
	t = int(input())
	for _ in range(t):
		(n, k) = map(int, input().split())
		weight = []
		cost = []
		ind = []
		res = 0
		for i in range(n):
			(c, w) = map(int, input().split())
			weight.append(w)
			cost.append(c)
			ind.append(i)
		maxk = -float('inf')
		for i in range(1, n + 1):
			for itert in combinations(ind, i):
				c = 0
				w = 0
				for j in itert:
					c += cost[j]
					w += weight[j]
				if c <= k:
					maxk = max(maxk, w)
		print(maxk)
except:
	pass


import itertools
t = int(input().strip())
for i in range(t):
	[n, k] = map(int, input().strip().split(' '))
	l = []
	for j in range(n):
		s = list(map(int, input().strip().split(' ')))
		l.append(s)
	l1 = []
	for L in range(0, n + 1):
		for i in itertools.combinations(l, L):
			l1.append(i)
	w2 = 0
	for j in range(len(l1)):
		p = l1[j]
		c1 = 0
		w1 = 0
		for m in range(len(p)):
			c1 += p[m][0]
			w1 += p[m][1]
		if c1 <= k:
			w2 = max(w2, w1)
	print(w2)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	app = []
	for i in range(n):
		(cost, weight) = map(int, input().split())
		app.append([cost, weight])
	maxi = 0

	def calc(curr):
		sm = 0
		ans = 0
		for i in curr:
			sm += app[i][0]
			ans += app[i][1]
		if sm <= k:
			return ans
		return 0
	tot = 1 << n
	for i in range(tot):
		curr = []
		for j in range(n):
			if i & 1 << j:
				curr.append(j)
		maxi = max(maxi, calc(curr))
	print(maxi)


def snek(l, a, k, s, b):
	if a == len(l):
		return s
	if b == 0:
		return max(snek(l, a + 1, k, s, 0), snek(l, a + 1, k, s, 1))
	if b == 1:
		if l[a][0] <= k:
			k -= l[a][0]
			s += l[a][1]
			return max(snek(l, a + 1, k, s, 0), snek(l, a + 1, k, s, 1))
		else:
			return s
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	l1 = []
	for j in range(n):
		l1.append(list(map(int, input().split())))
	print(max(snek(l1, 0, k, 0, 0), snek(l1, 0, k, 0, 1)))


import sys
from itertools import combinations as combn
stdin = sys.stdin
for (i, line) in enumerate(stdin):
	if i == 0:
		T = int(line.strip())
		N = -1
		oranges = []
		cur_i = 0
	elif cur_i > N:
		(N, K) = [int(s) for s in line.strip().split(' ')]
		oranges = []
		cur_i = 1
	else:
		oranges += [[int(s) for s in line.strip().split(' ')]]
		if cur_i == N:
			oranges = [[cost, weight] for (cost, weight) in oranges if cost <= K]
			max_weight = 0
			for size in range(1, len(oranges) + 1):
				baskets = [basket for basket in combn(oranges, size) if sum((cost for (cost, _) in basket)) <= K]
				if baskets:
					max_weight = max(max_weight, max((sum((weight for (_, weight) in basket)) for basket in baskets)))
			print(max_weight)
		cur_i += 1


def search(n, k, c, w):
	if k == 0:
		return 0
	elif n == 0:
		return 0
	elif k < c[n - 1]:
		return search(n - 1, k, c, w)
	else:
		return max(search(n - 1, k, c, w), w[n - 1] + search(n - 1, k - c[n - 1], c, w))
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	c = [0 for x in range(n)]
	w = [0 for y in range(n)]
	for j in range(n):
		(c[j], w[j]) = map(int, input().split())
	print(search(n, k, c, w))


def knapsack(k, c, w, n):
	if n == 0 or k == 0:
		return 0
	if c[n - 1] > k:
		return knapsack(k, c, w, n - 1)
	else:
		return max(w[n - 1] + knapsack(k - c[n - 1], c, w, n - 1), knapsack(k, c, w, n - 1))
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	cost = []
	weight = []
	for _ in range(n):
		(c, w) = map(int, input().split())
		cost.append(c)
		weight.append(w)
	print(knapsack(k, cost, weight, len(cost)))


def solve(W, wt, val, n):
	if n == 0 or W == 0:
		return 0
	if wt[n - 1] > W:
		return solve(W, wt, val, n - 1)
	else:
		return max(val[n - 1] + solve(W - wt[n - 1], wt, val, n - 1), solve(W, wt, val, n - 1))
for _ in range(int(input())):
	wt = []
	val = []
	(n, k) = map(int, input().split())
	for i in range(n):
		(x, y) = map(int, input().split())
		wt.append(x)
		val.append(y)
	print(solve(k, wt, val, n))


def solve(costs, weights, k, n):
	limit = 2 ** n
	ans = float('-inf')
	for i in range(1, limit):
		rep = '{:0' + str(n) + 'b}'
		rep = [int(x) for x in rep.format(i)]
		curr_sum = sum([x * y for (x, y) in zip(weights, rep)])
		curr_cost = sum([x * y for (x, y) in zip(costs, rep)])
		if curr_cost <= k:
			ans = max(ans, curr_sum)
	return ans
for t in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	costs = []
	weights = []
	for i in range(n):
		(a, b) = [int(x) for x in input().split()]
		costs.append(a)
		weights.append(b)
	print(solve(costs, weights, k, n))


def knapSack(W, wt, val, n):
	if n == 0 or W == 0:
		return 0
	if wt[n - 1] > W:
		return knapSack(W, wt, val, n - 1)
	else:
		return max(val[n - 1] + knapSack(W - wt[n - 1], wt, val, n - 1), knapSack(W, wt, val, n - 1))
t = int(input())
for i in range(t):
	(n, W) = map(int, input().split())
	val = []
	wt = []
	for i in range(n):
		(n1, m1) = map(int, input().split())
		val.append(m1)
		wt.append(n1)
	n = len(val)
	print(knapSack(W, wt, val, n))


def cal(l, a, k, s, b):
	if a == len(l):
		return s
	if b == 0:
		return max(cal(l, a + 1, k, s, 0), cal(l, a + 1, k, s, 1))
	if b == 1:
		if l[a][0] <= k:
			k -= l[a][0]
			s += l[a][1]
			return max(cal(l, a + 1, k, s, 0), cal(l, a + 1, k, s, 1))
		else:
			return s
for t in range(int(input())):
	(n, k) = map(int, input().split())
	list1 = []
	for i in range(n):
		list1.append(list(map(int, input().split())))
	print(max(cal(list1, 0, k, 0, 0), cal(list1, 0, k, 0, 1)))


for _ in range(int(input())):
	(n, k) = [int(c) for c in input().split()]
	costs = []
	weights = []
	for i in range(n):
		(c, w) = [int(c) for c in input().split()]
		costs.append(c)
		weights.append(w)
	maxweight = 0
	for i in range(1024):
		currcost = 0
		currweight = 0
		for j in range(n):
			if i & 1 << j:
				currcost += costs[j]
				currweight += weights[j]
		if currcost <= k:
			maxweight = max(maxweight, currweight)
	print(maxweight)


dp = dict()

def recur(cost, weight, n, k):
	if n in dp.keys():
		if k in dp[n].keys():
			return dp[n][k]
	if k == 0 or n == -1:
		return 0
	if cost[n] > k:
		return recur(cost, weight, n - 1, k)
	if n not in dp:
		dp[n] = dict()
	dp[n][k] = max(weight[n] + recur(cost, weight, n - 1, k - cost[n]), recur(cost, weight, n - 1, k))
	return dp[n][k]
tcase = int(input())
while tcase > 0:
	tcase -= 1
	(c, w) = ([], [])
	(n, k) = map(int, input().split())
	for _ in range(n):
		(cost, weight) = map(int, input().split())
		c.append(cost)
		w.append(weight)
	print(recur(c, w, n - 1, k))
	dp = dict()


from itertools import combinations
for _ in range(int(input())):
	(toranges, trubles) = list(map(int, input().split()))
	ocost_oweight = []
	for i in range(toranges):
		ocost_oweight.append(list(map(int, input().split())))
	pos_choices = []
	for i in range(1, toranges + 1):
		pos_choices.append(list(combinations(ocost_oweight, i)))
	pos_weights = []
	for choice_type in pos_choices:
		for choice in choice_type:
			weight = 0
			cost = 0
			feasible = True
			for pair in choice:
				weight += pair[1]
				cost += pair[0]
				if cost > trubles:
					feasible = False
					break
			if feasible:
				pos_weights.append(weight)
	print(max(pos_weights))


import itertools, sys
T = int(sys.stdin.readline())
for _ in range(T):
	(n, k) = list(map(int, sys.stdin.readline().split()))
	(cost, weight) = zip(*[list(map(int, sys.stdin.readline().split())) for _ in range(n)])
	weights = []
	for seq in itertools.product([0, 1], repeat=n):
		if sum((x * y for (x, y) in zip(seq, cost))) <= k:
			weights.append(sum((x * y for (x, y) in zip(seq, weight))))
	print(max(weights))


def bitmask(cost, wt, W, n):
	s = ''
	for i in range(n):
		s += '1'
	s = int(s, 2)
	ans = 0
	for i in range(1, s + 1):
		curr = i
		(curr_val, j) = (0, n - 1)
		curr_cost = W
		while curr != 0:
			if curr & 1:
				if curr_cost - cost[j] >= 0:
					curr_val += wt[j]
					curr_cost -= cost[j]
			j -= 1
			curr = curr >> 1
		ans = max(curr_val, ans)
	return ans
for _ in range(int(input())):
	(n, W) = map(int, input().split())
	(cost, wt) = ([], [])
	for i in range(n):
		(a, b) = map(int, input().split())
		cost.append(a)
		wt.append(b)
	ans = bitmask(cost, wt, W, n)
	print(ans)


def knapSack(W, wt, val, n):
	if n == 0 or W == 0:
		return 0
	if wt[n - 1] > W:
		return knapSack(W, wt, val, n - 1)
	else:
		return max(val[n - 1] + knapSack(W - wt[n - 1], wt, val, n - 1), knapSack(W, wt, val, n - 1))
t = int(input())
while t != 0:
	first = [int(i) for i in input().split()]
	n = first[0]
	k = first[1]
	cost = []
	weight = []
	for i in range(n):
		sec = [int(i) for i in input().split()]
		cost.append(sec[0])
		weight.append(sec[1])
	print(knapSack(k, cost, weight, n))
	t -= 1


def knapsack(W, cost, wt, n):
	if n < 0 or W == 0:
		return 0
	if cost[n] > W:
		return knapsack(W, cost, wt, n - 1)
	else:
		inc = wt[n] + knapsack(W - cost[n], cost, wt, n - 1)
		exc = knapsack(W, cost, wt, n - 1)
		return max(inc, exc)
for _ in range(int(input())):
	(n, W) = map(int, input().split())
	(cost, wt) = ([], [])
	for i in range(n):
		(a, b) = map(int, input().split())
		cost.append(a)
		wt.append(b)
	ans = knapsack(W, cost, wt, n - 1)
	print(ans)


T = int(input())
for t in range(T):
	(n, k) = [int(i) for i in input().split(' ')]
	C = []
	W = []
	for X in range(n):
		(c, w) = [int(i) for i in input().split(' ')]
		C.append(c)
		W.append(w)
	maxwt = 0
	for i in range(1 << n):
		curwt = 0
		curcost = 0
		for j in range(n):
			if i & 1 << j:
				curcost += C[j]
				curwt += W[j]
		if curcost <= k:
			maxwt = max(maxwt, curwt)
	print(maxwt)


memo = dict()

def knpsk(c, w, index, k):
	if index in memo.keys():
		if k in memo[index].keys():
			return memo[index][k]
	if k == 0 or index == -1:
		return 0
	if c[index] > k:
		return knpsk(c, w, index - 1, k)
	if index not in memo:
		memo[index] = dict()
	memo[index][k] = max(w[index] + knpsk(c, w, index - 1, k - c[index]), knpsk(c, w, index - 1, k))
	return memo[index][k]
tcase = int(input())
while tcase > 0:
	tcase -= 1
	(c, w) = ([], [])
	(n, k) = map(int, input().split())
	for i in range(n):
		(cost, weight) = map(int, input().split())
		c.append(cost)
		w.append(weight)
	print(knpsk(c, w, n - 1, k))
	memo = dict()


def make_set(arr, l):
	ans = []
	for i in range(2 ** l):
		bits = bin(i)[2:]
		bits = '0' * (l - len(bits)) + bits
		temp = []
		for x in range(l):
			if bits[x] == '1':
				temp += [arr[x]]
		ans += [temp]
	return ans
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	arr = []
	for j in range(n):
		(c, w) = map(int, input().split())
		arr += [[c, w]]
	s = make_set(arr, n)
	maxw = 0
	for j in s:
		cost = 0
		weight = 0
		for x in j:
			weight += x[1]
			cost += x[0]
		if weight > maxw and cost <= k:
			maxw = weight
	print(maxw)


ans = []

def solve(id, remW):
	if remW <= 0 or id == n:
		return 0
	marker = (id, remW)
	if marker in memo:
		return memo[marker]
	ans = solve(id + 1, remW)
	if remW >= pairs[id][0]:
		ans = max(ans, solve(id + 1, remW - pairs[id][0]) + pairs[id][1])
	memo[marker] = ans
	return ans
for t in range(int(input())):
	[n, k] = [int(i) for i in input().split()]
	memo = {}
	pairs = []
	for i in range(n):
		pairs.append([int(i) for i in input().split()])
	ans.append(str(solve(0, k)))
print('\n'.join(ans))