You have N items that you want to put them into a knapsack. Item i has value vi and weight wi.

You want to find a subset of items to put such that:

* The total value of the items is as large as possible.
* The items have combined weight at most W, that is capacity of the knapsack.



Find the maximum total value of items in the knapsack.

Constraints

* 1 ≤ N ≤ 100
* 1 ≤ vi ≤ 100
* 1 ≤ wi ≤ 10,000,000
* 1 ≤ W ≤ 1,000,000,000

Input


N W
v1 w1
v2 w2
:
vN wN


The first line consists of the integers N and W. In the following N lines, the value and weight of the i-th item are given.

Output

Print the maximum total values of the items in a line.

Examples

Input

4 5
4 2
5 2
2 1
8 3


Output

13


Input

2 20
5 9
4 10


Output

9

Source: aizu | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
(n, m) = map(int, input().split())
VW = [tuple(map(int, input().split())) for i in range(n)]
V = [v for (v, w) in VW]
W = [w for (v, w) in VW]
sv = sum(V)
inf = 10 ** 10
DP = [[inf for j in range(sv + 1)] for i in range(n + 1)]
DP[0][0] = 0
for i in range(n):
	for j in range(sv + 1):
		if j < V[i]:
			DP[i + 1][j] = DP[i][j]
		else:
			DP[i + 1][j] = min(DP[i][j], DP[i][j - V[i]] + W[i])
for j in range(sv, 0, -1):
	if DP[n][j] <= m:
		print(j)
		exit()
print(0)


import sys
from collections import namedtuple
MAX_V = 100

def solve():
	dp = [[float('inf')] * (c_items * MAX_V + 1) for _ in range(c_items + 1)]
	dp[0][0] = 0
	for (i, item) in enumerate(item_list):
		(v, w) = (item.value, item.weight)
		for j in range(c_items * MAX_V + 1):
			if j < v:
				dp[i + 1][j] = dp[i][j]
			else:
				dp[i + 1][j] = min(dp[i][j], dp[i][j - v] + w)
	ans = 0
	res_list = dp[-1]
	for i in range(c_items * MAX_V + 1):
		if res_list[i] <= knapsack_cp:
			ans = i
	return ans
_input = sys.stdin.readlines()
(c_items, knapsack_cp) = map(int, _input[0].split())
items = map(lambda x: x.split(), _input[1:])
Item = namedtuple('Item', ('value', 'weight'))
item_list = [Item(int(v), int(w)) for (v, w) in items]
print(solve())


import sys
MAX_V = 100 ** 2
(N, W) = map(lambda x: int(x), input().split())
dp = [sys.maxsize] * (MAX_V + 1)
dp[0] = 0
for i in range(N):
	(value, weight) = map(lambda x: int(x), input().split())
	for v in range(MAX_V, 0, -1):
		if v - value < 0:
			break
		dp[v] = min(dp[v], dp[v - value] + weight)
ans = 0
for v in range(MAX_V, 0, -1):
	if dp[v] <= W:
		ans = v
		break
print(ans)


(N, W) = map(int, input().split())
V = 100 * N
Data = []
for _ in range(N):
	(v, w) = map(int, input().split())
	Data.append([v, w])
INF = 10 ** 12
DP = [[INF] * (V + 1) for _ in range(N + 1)]
for i in range(N + 1):
	DP[i][0] = 0
for n in range(1, N + 1):
	for v in range(1, V + 1):
		(tv, tw) = Data[n - 1]
		if tv <= v:
			DP[n][v] = min(DP[n][v], DP[n - 1][v - tv] + tw)
		DP[n][v] = min(DP[n][v], DP[n - 1][v])
res = 0
for v in range(1, V + 1):
	w = DP[N][v]
	if w <= W:
		res = v
print(res)


import sys
import math
import collections
import bisect
import itertools
import fractions
import copy
import decimal
import queue
sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
ni = lambda : int(sys.stdin.readline())
ns = lambda : map(int, sys.stdin.readline().split())
na = lambda : list(map(int, sys.stdin.readline().split()))

def main():
	(n, w) = ns()
	dp = [INF for _ in range(n * 100 + 1)]
	dp[0] = 0
	for _ in range(n):
		(vi, wi) = ns()
		for i in range(n * 100 - vi, -1, -1):
			if dp[i] == INF:
				continue
			if dp[i] + wi <= w:
				dp[i + vi] = min(dp[i + vi], dp[i] + wi)
	for i in range(n * 100, -1, -1):
		if dp[i] != INF:
			print(i)
			exit(0)
main()


import sys, bisect
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 7)
INF = 10 ** 10

def I():
	return int(input())

def F():
	return float(input())

def SS():
	return input()

def LI():
	return [int(x) for x in input().split()]

def LI_():
	return [int(x) - 1 for x in input().split()]

def LF():
	return [float(x) for x in input().split()]

def LSS():
	return input().split()

def resolve():
	(N, W) = LI()
	vw = [LI() for _ in range(N)]
	v_sum = sum([i[0] for i in vw])
	dp = [[INF] * (v_sum + 1) for _ in range(N + 1)]
	for i in range(N + 1):
		dp[i][0] = 0
	for i in range(N):
		for j in range(v_sum):
			v_p = max(j + 1 - vw[i][0], 0)
			if v_p >= 0:
				dp[i + 1][j + 1] = min(dp[i][j + 1], dp[i][v_p] + vw[i][1])
			else:
				dp[i + 1][j + 1] = dp[i][j + 1]
	ans = bisect.bisect_right(dp[-1], W) - 1
	print(ans)
resolve()


(N, W) = [int(t) for t in input().split()]
item = [tuple((int(t) for t in input().split())) for _ in range(N)]
MAX_V = sum((v for (v, w) in item))
weight = {u: float('inf') for u in range(MAX_V + 1)}
weight[0] = 0
for (v, w) in item:
	weight = {u: min(weight[u - v] + w, weight[u]) if u >= v else weight[u] for u in range(MAX_V + 1)}
v = max((v for v in weight if weight[v] <= W))
print(v)


import sys
from collections import namedtuple
(MAX_N, MAX_V) = (100, 100)

def solve():
	dp = [[float('inf')] * (MAX_N * MAX_V + 1) for _ in range(MAX_N + 1)]
	dp[0][0] = 0
	for (i, item) in enumerate(item_list):
		(v, w) = (item.value, item.weight)
		for j in range(MAX_N * MAX_V + 1):
			if j < v:
				dp[i + 1][j] = dp[i][j]
			else:
				dp[i + 1][j] = min(dp[i][j], dp[i][j - v] + w)
	ans = 0
	for i in range(MAX_N * MAX_V + 1):
		if dp[c_items][i] <= real_cp:
			ans = i
	return ans
_input = sys.stdin.readlines()
(c_items, real_cp) = map(int, _input[0].split())
items = map(lambda x: x.split(), _input[1:])
Item = namedtuple('Item', ('value', 'weight'))
item_list = [Item(int(v), int(w)) for (v, w) in items]
print(solve())


from collections import defaultdict
INF = 10 ** 10

def main():
	(N, W) = map(int, input().split())
	items = []
	for _ in range(N):
		(v, w) = map(int, input().split())
		items.append((v, w))
	dp = [[INF] * (N * 100 + 1) for _ in range(N + 1)]
	dp[0][0] = 0
	for i in range(N):
		(v, w) = items[i]
		for j in range(len(dp[0])):
			if dp[i][j] != INF:
				dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
				dp[i + 1][j + v] = min(dp[i + 1][j + v], dp[i][j] + w)
	ans = 0
	for i in range(len(dp)):
		for j in range(len(dp[0])):
			if dp[i][j] <= W:
				ans = max(ans, j)
	print(ans)
main()


import sys
readline = sys.stdin.readline
(N, W) = map(int, readline().split())
inf = float('inf')
dp = [inf] * (N * 100 + 1)
dp[0] = 0
s = {0}
for i in range(N):
	(v, w) = map(int, readline().split())
	for _v in sorted(s, reverse=True):
		new_w = dp[_v] + w
		if new_w <= W:
			new_v = v + _v
			dp[new_v] = new_w if new_w < dp[new_v] else dp[new_v]
			s.add(new_v)
for i in range(N * 100, -1, -1):
	if dp[i] < inf:
		print(i)
		break


(N, W) = map(int, input().split())
v = [0] * N
w = [0] * N
for i in range(N):
	(v[i], w[i]) = map(int, input().split())
V = max(v) * N
dp = [-1] * (V + 1)
dp[0] = 0
for i in range(N):
	for j in range(V + 1):
		if dp[V - j] != -1 and -j + v[i] <= 0:
			if dp[V - j + v[i]] == -1:
				dp[V - j + v[i]] = dp[V - j] + w[i]
			else:
				dp[V - j + v[i]] = min(dp[V - j + v[i]], dp[V - j] + w[i])
for i in range(V + 1):
	if dp[V - i] != -1 and dp[V - i] <= W:
		print(V - i)
		break


iim = lambda : map(int, input().rstrip().split())

def resolve():
	(N, W) = iim()
	S = [list(iim()) for i in range(N)]
	NV = N * 100 + 1
	Inf = float('inf')
	dp = [Inf] * (NV + 1)
	dp[0] = 0
	ans = 0
	for (v, w) in S:
		for i in range(ans, -1, -1):
			j = i + v
			w2 = dp[i] + w
			if dp[i] == Inf:
				continue
			if w2 > W:
				continue
			dp[j] = min(dp[j], w2)
			ans = max(ans, j)
	print(ans)
resolve()


def KP(Val, Wei, N, W):
	v_sum = sum(Val)
	INF = 10 ** 9 + 1
	dp = [[INF for _ in range(v_sum + 1)] for _ in range(N + 1)]
	for i in range(N + 1):
		dp[i][0] = 0
	for i in range(N):
		for j in range(v_sum + 1):
			if j - Val[i] >= 0:
				dp[i + 1][j] = min(dp[i][j - Val[i]] + Wei[i], dp[i][j])
			else:
				dp[i + 1][j] = dp[i][j]
	output = 0
	for j in range(v_sum + 1):
		if dp[N][j] <= W:
			output = j
	return output

def main():
	(N, W) = map(int, input().split())
	VW = [list(map(int, input().split())) for _ in range(N)]
	Val = [VW[i][0] for i in range(N)]
	Wei = [VW[i][1] for i in range(N)]
	ans = KP(Val, Wei, N, W)
	print(ans)
main()


INF = 10 ** 20

def sack(N, W, vlist, wlist):
	sum_val = sum(vlist)
	global INF
	dp = [INF for i in range(sum_val + 1)]
	dp[0] = 0
	for i in range(N):
		for j in range(sum_val, vlist[i] - 1, -1):
			dp[j] = min(dp[j], dp[j - vlist[i]] + wlist[i])
	for j in range(sum_val, -1, -1):
		if dp[j] <= W:
			return j
			break
(N, W) = map(int, input().split())
vlist = []
wlist = []
for i in range(N):
	(v, w) = map(int, input().split())
	vlist.append(v)
	wlist.append(w)
print(sack(N, W, vlist, wlist))


import heapq
from collections import deque
from enum import Enum
import sys
import math
from _heapq import heappush, heappop
BIG_NUM = 2000000000
MOD = 1000000007
EPS = 1e-09
NUM = 10000
(N, W) = map(int, input().split())
dp = [W + 1] * (NUM + 1)
dp[0] = 0
for loop in range(N):
	(value, weight) = map(int, input().split())
	for v in range(NUM, 0, -1):
		if v - value < 0:
			break
		dp[v] = min(dp[v], dp[v - value] + weight)
ans = 0
for i in range(NUM, 0, -1):
	if dp[i] <= W:
		ans = i
		break
print('%d' % ans)


import sys
import collections

def solve():
	(N, W) = map(int, sys.stdin.readline().split())
	vw = tuple((tuple(map(int, sys.stdin.readline().split())) for _ in range(N)))
	dp = {}
	dp[0] = 0
	for (v, w) in vw:
		temp = dp.copy()
		for j in list(dp.keys()):
			if j + w <= W and (not j + w in dp or dp[j + w] < dp[j] + v):
				temp[j + w] = dp[j] + v
		dp = temp
	print(max(dp.values()))

def solve1():
	(N, W) = map(int, sys.stdin.readline().split())
	vw = tuple((tuple(map(int, sys.stdin.readline().split())) for _ in range(N)))
	V = sum((v for (v, _) in vw))
	dp = [W + 1] * (V + 1)
	dp[0] = 0
	for (v, w) in vw:
		for c_v in range(V + 1)[::-1]:
			if 0 <= c_v - v:
				dp[c_v] = min(dp[c_v], dp[c_v - v] + w)
	for c_v in range(V + 1)[::-1]:
		if dp[c_v] <= W:
			return c_v
	return V
print(solve1())


def max_value(total_weight, items):
	total_value = sum([v for (v, _) in items])
	ws = [total_weight + 1] * (total_value + 1)
	ws[0] = 0
	for item in sorted(items):
		(v, w) = item
		for i in reversed(range(total_value - v + 1)):
			ws[i + v] = min(ws[i + v], ws[i] + w)
	return max([i for (i, w) in enumerate(ws) if w <= total_weight])

def run():
	(n, t) = [int(i) for i in input().split()]
	vs = []
	for _ in range(n):
		(v, w) = [int(i) for i in input().split()]
		vs.append((v, w))
	print(max_value(t, vs))
run()


(N, W) = map(int, input().split())
item = [list(map(int, input().split())) for _ in range(N)]
V = sum(map(lambda x: x[0], item))
dp = [W + 1 for _ in range(V + 1)]
dp[0] = 0
for i in range(N):
	(v, w) = item[i]
	for j in range(V + 1)[::-1]:
		if j - v >= 0:
			dp[j] = min(dp[j - v] + w, dp[j])
print(max((j for j in range(V + 1) if dp[j] <= W)))


(N, W) = map(int, input().split())
v = [0] * N
w = [0] * N
for i in range(N):
	(v[i], w[i]) = list(map(int, input().split()))
INF = float('inf')
dp = [[INF] * (sum(v) + 1) for _ in range(N + 1)]
dp[0][0] = 0
for i in range(N):
	for j in range(sum(v) + 1):
		if j - v[i] >= 0:
			dp[i + 1][j] = min(dp[i][j], dp[i][j - v[i]] + w[i])
		else:
			dp[i + 1][j] = dp[i][j]
ans = 0
cnt = -1
for i in dp[-1]:
	cnt += 1
	if i <= W:
		ans = cnt
print(ans)


(N, W) = map(int, input().split())
I = [list(map(int, input().split())) for i in range(N)]
V = sum((v for (v, w) in I))
dp = [W + 1] * (V + 1)
dp[0] = 0
for (v, w) in I:
	for j in range(V, v - 1, -1):
		dp[j] = min(dp[j - v] + w, dp[j])
print(max((i for i in range(V + 1) if dp[i] <= W)))


import sys
input = sys.stdin.readline
(N, W) = [int(x) for x in input().split()]
items = []
sum_value = 0
for i in range(N):
	(v, w) = map(int, input().split())
	items += [(v, w)]
	sum_value += v
dp = [0] + [float('inf')] * sum_value
for i in range(N):
	(v, w) = items[i]
	for j in reversed(range(v, sum_value + 1)):
		dp[j] = min(dp[j], dp[j - v] + w)
for j in reversed(range(sum_value + 1)):
	if dp[j] <= W:
		print(j)
		break


import bisect
(n, W) = map(int, input().split())
b = [list(map(int, input().split())) for i in range(n)]
dp = [float('INF') for i in range(10001)]
dp[0] = 0
for (v, w) in b:
	for i in range(10001):
		if 10000 - i + v < 10001:
			dp[10000 - i + v] = min(dp[10000 - i + v], dp[10000 - i] + w)
for i in range(1, 10000):
	dp[10000 - i] = min(dp[10000 - i], dp[10001 - i])
print(bisect.bisect_right(dp, W) - 1)


(N, W) = [int(x) for x in input().split()]
vs = [0] * N
ws = [0] * N
for i in range(N):
	(vs[i], ws[i]) = [int(x) for x in input().split()]
vmax = sum(vs) + 1
dp = [[float('inf')] * vmax for x in range(N + 1)]
dp[0][0] = 0
for i in range(1, N + 1):
	v = vs[i - 1]
	w = ws[i - 1]
	for j in range(vmax):
		if j < v:
			dp[i][j] = dp[i - 1][j]
		else:
			dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - v] + w)
print(max((i for (i, x) in enumerate(dp[N]) if x <= W)))


(N, W) = map(int, input().split())
goods = [list(map(int, input().split())) for i in range(N)]
v_sum = sum([i[0] for i in goods])
dp = [float('inf') for i in range(v_sum + 1)]
dp[0] = 0
for i in range(N):
	for j in range(v_sum, -1, -1):
		dp[j] = min(dp[j - goods[i][0]] + goods[i][1], dp[j])
for i in range(v_sum, -1, -1):
	if dp[i] <= W:
		print(i)
		break


import sys
from collections import namedtuple
MAX_V = 100

def solve():
	dp = [[float('inf')] * (c_items * MAX_V + 1) for _ in range(c_items + 1)]
	dp[0][0] = 0
	for (i, item) in enumerate(item_list):
		(v, w) = (item.value, item.weight)
		for j in range(c_items * MAX_V + 1):
			if j < v:
				dp[i + 1][j] = dp[i][j]
			else:
				dp[i + 1][j] = min(dp[i][j], dp[i][j - v] + w)
	ans = 0
	for i in range(c_items * MAX_V + 1):
		if dp[c_items][i] <= knapsack_cp:
			ans = i
	return ans
_input = sys.stdin.readlines()
(c_items, knapsack_cp) = map(int, _input[0].split())
items = map(lambda x: x.split(), _input[1:])
Item = namedtuple('Item', ('value', 'weight'))
item_list = [Item(int(v), int(w)) for (v, w) in items]
print(solve())


def knapsack(n, w, info):
	sum_v = 0
	for i in range(n):
		value = info[i][0]
		sum_v += value
	dp = [[float('inf')] * (sum_v + 1) for i in range(n + 1)]
	dp[0][0] = 0
	for i in range(n):
		for j in range(sum_v + 1):
			weight = info[i][1]
			value = info[i][0]
			if j < value:
				dp[i + 1][j] = dp[i][j]
			else:
				dp[i + 1][j] = min(dp[i][j], dp[i][j - value] + weight)
	ans = 0
	for j in range(sum_v + 1):
		if dp[n][j] <= w:
			ans = j
	return ans
(n, w) = map(int, input().split())
info = [list(map(int, input().split())) for i in range(n)]
print(knapsack(n, w, info))


import sys
input = sys.stdin.readline
(M, W) = map(int, input().split())
single = True
price_list = [0]
weight_list = [0]
for _ in range(M):
	(price, weight) = map(int, input().split())
	price_list.append(price)
	weight_list.append(weight)
V = sum(price_list)
dp_max = W + 1
dp = [[dp_max] * (V + 1) for _ in range(M + 1)]
for item in range(M + 1):
	dp[item][0] = 0
for item in range(1, M + 1):
	for price in range(1, V + 1):
		if price < price_list[item]:
			dp[item][price] = dp[item - 1][price]
		else:
			temp = dp[item - single][price - price_list[item]] + weight_list[item]
			if temp < dp[item - 1][price]:
				dp[item][price] = temp
			else:
				dp[item][price] = dp[item - 1][price]
print(max((price for price in range(V + 1) if dp[M][price] <= W)))


import sys
from sys import stdin
from collections import namedtuple
input = stdin.readline

def solve(items, W, max_v):
	n = len(items)
	dp = [[float('inf')] * (n * max_v + 1) for _ in range(n + 1)]
	dp[0][0] = 0
	for (i, item) in enumerate(items):
		for j in range(n * max_v + 1):
			if j < item.v:
				dp[i + 1][j] = dp[i][j]
			else:
				dp[i + 1][j] = min(dp[i][j], dp[i][j - item.v] + item.w)
	for j in range(n * max_v + 1):
		if dp[n][j] <= W:
			result = j
	return result
item = namedtuple('item', ['v', 'w'])

def main(args):
	(N, W) = map(int, input().split())
	items = []
	for _ in range(N):
		(v, w) = map(int, input().split())
		items.append(item(v, w))
	items.sort()
	max_v = items[-1].v
	result = solve(items, W, max_v)
	print(result)
main(sys.argv[1:])


def main():
	(N, W) = map(int, input().split())
	(values, weights) = ([], [])
	for i in range(N):
		(v, w) = map(int, input().split())
		values.append(v)
		weights.append(w)
	INF = 10 ** 11
	MAX_VALUE = 100 * N
	dp = [[INF for i in range(MAX_VALUE + 1)] for j in range(N + 1)]
	dp[0][0] = 0
	for i in range(N):
		for j in range(MAX_VALUE + 1):
			if values[i] > j:
				dp[i + 1][j] = dp[i][j]
			else:
				dp[i + 1][j] = min(dp[i][j], dp[i][j - values[i]] + weights[i])
	ans = 0
	for i in range(MAX_VALUE + 1):
		if dp[N][i] <= W:
			ans = i
	print(ans)
main()


(n, w) = map(int, input().split())
vw = [input().split() for _ in range(n)]
vw = [(int(x[0]), int(x[1])) for x in vw]
v_max = sum([x[0] for x in vw])
INF = 10 ** 9 + 1
pdp = [INF for _ in range(v_max + 1)]
cdp = [INF for _ in range(v_max + 1)]
pdp[0] = 0
cdp[0] = 0
for i in range(n):
	for j in range(v_max + 1):
		if j + vw[i][0] < v_max + 1:
			cdp[j + vw[i][0]] = min(pdp[j + vw[i][0]], pdp[j] + vw[i][1])
		else:
			break
	pdp = cdp[:]
ans = INF
for i in range(len(cdp)):
	if cdp[i] <= w:
		ans = i
print(ans)


import sys
sys.setrecursionlimit(10 ** 6)
from bisect import *
from collections import *
from heapq import *
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.readline())

def SI():
	return sys.stdin.readline()[:-1]

def MI():
	return map(int, sys.stdin.readline().split())

def MI1():
	return map(int1, sys.stdin.readline().split())

def MF():
	return map(float, sys.stdin.readline().split())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LI1():
	return list(map(int1, sys.stdin.readline().split()))

def LF():
	return list(map(float, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]
dij = [(0, 1), (1, 0), (0, -1), (-1, 0)]

def main():
	inf = 10 ** 9 + 5
	(n, wn) = MI()
	dp = [inf] * 10005
	dp[0] = 0
	for _ in range(n):
		(v, w) = MI()
		for i in range(10004, -1, -1):
			if i - v < 0:
				break
			dp[i] = min(dp[i], dp[i - v] + w)
	for i in range(10004, -1, -1):
		if dp[i] <= wn:
			print(i)
			break
main()


(N, W) = map(int, input().split())
VW = [list(map(int, input().split())) for _ in range(N)]
inf = float('inf')
dp = [[inf] * 100001 for _ in range(N + 1)]
dp[0][0] = 0
for i in range(N):
	(v, w) = VW[i]
	for p in range(0, 10001):
		dp[i + 1][p + v] = min(dp[i + 1][p + v], dp[i][p] + w)
		dp[i + 1][p] = min(dp[i + 1][p], dp[i][p])
ans = 0
for (i, w) in enumerate(dp[N]):
	if w <= W:
		ans = max(ans, i)
print(ans)


INF = 10 ** 20
(n, w) = map(int, input().split())
value = []
weight = []
for _ in range(n):
	(vi, wi) = map(int, input().split())
	value.append(vi)
	weight.append(wi)
sum_value = sum(value)
dp = [INF for _ in range(sum_value + 1)]
dp[0] = 0
for i in range(n):
	for j in range(sum_value, value[i] - 1, -1):
		dp[j] = min(dp[j], dp[j - value[i]] + weight[i])
for j in range(sum_value, -1, -1):
	if dp[j] <= w:
		print(j)
		break


from math import isfinite
from itertools import dropwhile
(n, knapsack) = map(int, input().split())
dpn = n * 100
dp = [float('inf')] * (dpn + 1)
dp[0] = 0
for i in range(n):
	(value, weight) = map(int, input().split())
	for j in range(dpn - value, 0, -1):
		if not isfinite(dp[j]):
			continue
		new_weight = dp[j] + weight
		if new_weight <= knapsack and dp[j + value] > new_weight:
			dp[j + value] = new_weight
	if weight <= knapsack and dp[value] > weight:
		dp[value] = weight
print(next(dropwhile(lambda i: not isfinite(dp[i]), range(dpn, -1, -1))))


def knapsack_val(W, items):
	N = len(items)
	INF = 10 ** 12
	MAX_V = sum([v for (_, v) in items])
	dp = [[INF for j in range(MAX_V + 1)] for i in range(N + 1)]
	dp[0][0] = 0
	for i in range(1, N + 1):
		(w, v) = items[i - 1]
		for j in range(MAX_V + 1):
			if j - v >= 0:
				dp[i][j] = min(dp[i - 1][j - v] + w, dp[i - 1][j])
			else:
				dp[i][j] = dp[i - 1][j]
	for v in range(MAX_V, -1, -1):
		if dp[N][v] <= W:
			break
	return v
(N, W) = map(int, input().split())
items = []
for _ in range(N):
	(v, w) = map(int, input().split())
	items.append((w, v))
print(knapsack_val(W, items))


from math import isfinite
(n, knapsack) = map(int, input().split())
dpn = n * 100
dp = [float('inf')] * (dpn + 1)
dp[0] = 0
for i in range(n):
	(value, weight) = map(int, input().split())
	for j in range(dpn - value, -1, -1):
		if not isfinite(dp[j]):
			continue
		new_weight = dp[j] + weight
		if new_weight <= knapsack and dp[j + value] > new_weight:
			dp[j + value] = new_weight
print(next(filter(lambda i: isfinite(dp[i]), range(dpn, -1, -1))))


(n, w_max) = map(int, input().split())
v = []
w = []
for _ in range(n):
	(v_in, w_in) = map(int, input().split())
	v.append(v_in)
	w.append(w_in)
v_max = sum(v)
lrg = 100000000000001
DP = [lrg] * (v_max * 2)
DP[0] = 0
for i in range(n):
	for u in range(v_max, 0, -1):
		DP[u] = min(DP[u], DP[u - v[i]] + w[i])
ans = []
for u in range(v_max + 1):
	if DP[u] <= w_max:
		ans.append(u)
print(max(ans))


(N, W) = map(int, input().split())
values = []
weights = []
for i in range(N):
	item = list(map(int, input().split()))
	values.append(item[0])
	weights.append(item[1])
max_value = sum(values)
dp = [[float('inf') for value in range(max_value + 1)] for i in range(N + 1)]
dp[0][0] = 0
for i in range(N):
	for value in range(max_value + 1):
		if value >= values[i]:
			dp[i + 1][value] = min(dp[i][value - values[i]] + weights[i], dp[i][value])
		else:
			dp[i + 1][value] = dp[i][value]
for value in range(max_value, 0, -1):
	if dp[N][value] <= W:
		print(value)
		exit()
print(0)


(N, W) = map(int, input().split())
I = [list(map(int, input().split())) for _ in range(N)]
MAX_V = sum((v for (v, _) in I))
dp = [W + 1] * (MAX_V + 1)
dp[0] = 0
for (v, w) in I:
	for j in range(MAX_V, v - 1, -1):
		dp[j] = min(dp[j - v] + w, dp[j])
for i in range(MAX_V, -1, -1):
	if dp[i] <= W:
		print(i)
		break


(N, W, *L) = map(int, open(0).read().split())
dp = [float('inf')] * 10001
dp[0] = 0
for (v, w) in zip(*[iter(L)] * 2):
	for i in range(10000, v - 1, -1):
		dp[i] = min(dp[i], dp[i - v] + w)
ans = 0
for v in range(10001):
	if dp[v] <= W:
		ans = max(ans, v)
print(ans)


def solve():
	from sys import stdin
	f_i = stdin
	(N, W) = map(int, f_i.readline().split())
	vw = tuple((tuple(map(int, f_i.readline().split())) for i in range(N)))
	size = sum((vw_i[0] for vw_i in vw))
	inf = 10 ** 9
	dp = [inf] * (size + 1)
	dp[-1] = 0
	for (v, w) in vw:
		for (i, tpl) in enumerate(zip(dp[v:], dp)):
			(w1, w2) = tpl
			w1 += w
			if w1 < w2:
				dp[i] = w1
	ans = 0
	for (i, w) in enumerate(dp[-2::-1], start=1):
		if w <= W:
			ans = i
	print(ans)
solve()


(N, W) = map(int, input().split())
(INF, V) = (1 << 40, 100)
dp = [[INF for j in range(N * V + 1)] for i in range(N + 1)]

def main():
	(v, w) = ([0 for i in range(N)], [0 for i in range(N)])
	for i in range(N):
		(v[i], w[i]) = map(int, input().split())
	dp[0][0] = 0
	for i in range(1, N + 1):
		for j in range(N * V + 1):
			if j < v[i - 1]:
				dp[i][j] = dp[i - 1][j]
			else:
				dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - v[i - 1]] + w[i - 1])
	ans = 0
	for i in range(N * V + 1):
		if dp[N][i] <= W:
			ans = i
	print(ans)
main()


(N, W) = map(int, input().split())
vs = []
ws = []
for i in range(N):
	(v, w) = map(int, input().split())
	vs.append(v)
	ws.append(w)
dp = dict()
dp[0] = 0
max_v = 0
for i in range(N):
	tmp = dp.copy()
	for (k, v) in tmp.items():
		dp.setdefault(k + vs[i], float('inf'))
		dp[k + vs[i]] = min(v + ws[i], dp[k + vs[i]])
		if dp[k + vs[i]] <= W:
			max_v = max(max_v, k + vs[i])
print(max_v)


(N, W) = map(int, input().split())
dp = [0] + [W + 1] * (N * 100)
for i in range(N):
	(v, w) = map(int, input().split())
	for j in range(i * 100, -1, -1):
		if dp[j + v] > dp[j] + w:
			dp[j + v] = dp[j] + w
for (v, w) in zip(range(N * 100, -1, -1), dp[::-1]):
	if w < W + 1:
		print(v)
		break