CodeEff/ECCO huggingface dataset:
# Original solution
import sys
#from collections import defaultdict
n, limit= list(map(int, sys.stdin.readline().split()))
L = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

#各重さとi番目の荷物を入れ終わった状態のテーブルをつくる
d = {}
dp = [d.copy() for _ in range(n)]

#初期状態
for w in range(L[0][0], limit+1):
    dp[0][w] = L[0][1]
#print(dp)
for i in range(1, n):
    for w in range(1, limit+1):
        if dp[i-1].get(w-L[i][0]) and dp[i-1].get(w): #キーが存在するなら
            dp[i][w] = max(dp[i-1][w-L[i][0]] + L[i][1], dp[i-1][w])
        elif dp[i-1].get(w) and w==L[i][0]:
            dp[i][w] = max(L[i][1], dp[i-1][w])
        elif dp[i-1].get(w):
            dp[i][w] = dp[i-1][w]
        elif w==L[i][0]:
            dp[i][w] = L[1][1]
    #print(dp)  
print((max(dp[-1].values())))

# Optimized solution
import sys
n, limit = list(map(int, sys.stdin.readline().split())) 
L = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

dp = [dict() for i in range(n)]
#print(dp)
dp[0][L[0][1]] = L[0][0]

for i in range(1, n):
    dp[i][L[i][1]] = min(L[i][0], dp[i-1].get(L[i][1], float('inf')))
    for v, w in list(dp[i-1].items()):
        dp[i][v] = min(dp[i-1][v], dp[i].get(v, float('inf')))
        dp[i][L[i][1] + v] = min(L[i][0] + dp[i-1][v], dp[i-1].get(L[i][1] + v, float('inf'))) 
        
ans = 0
for v, w in list(dp[-1].items()):
    if w <=limit:
        if ans < v:
            ans = v
#print(dp)
print(ans)
# Original solution
import sys
n, limit = list(map(int, sys.stdin.readline().split()))
L = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
#print(L)
dp = [{} for i in range(n+1)]

for i in range(n):
    Lw, Lv =L[i][0], L[i][1] #①i番目の価値を重さテーブルに代入
    dp[i+1][Lw] = Lv 
    for w, v in list(dp[i].items()):
        dp[i+1][w] = max(dp[i+1].get(w, 0), v) #② 一つ上の行の価値と比べて大きい方を代入
        if w + Lw <=limit:
            dp[i+1][w+Lw] = max(dp[i].get(w+ Lw, 0), Lv + v) #③一つ上の行の価値をループで1つづつ取り出し、i番目の価値と足し合わせる
        
print((max(dp[-1].values())))

# Optimized solution
import sys
n, limit = list(map(int, sys.stdin.readline().split()))
L = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
#print(L)
dp = [{} for i in range(n+1)]

for i in range(n):
    Lw, Lv = L[i][0], L[i][1] 
    dp[i+1][Lv] = min(Lw, dp[i].get(Lv, Lw))          #価値テーブルに重量を入れる
    for v, w in list(dp[i].items()):
        dp[i+1][v] = min(w, dp[i+1].get(v, w)) #上下比較
        tmp_w= min(Lw+ w, dp[i+1].get(Lv+v, Lw+w))
        if tmp_w <=limit:
            dp[i+1][Lv+ v] = tmp_w
        
print((max(dp[-1].keys())))
# Original solution
import sys
import bisect


def input():
    return sys.stdin.readline().rstrip()


def main():
    N, W = list(map(int, input().split()))
    vsup = 10 ** 3 * N + 2
    dp = [10 ** 12 + 1] * (vsup)  # 価値の総和を i (以上にするための重さの最小値
    dp[0] = 0

    for i in range(N):
        w, v = list(map(int, input().split()))
        for j in range(vsup-2, -1, -1):
            if j - v >= 0:
                dp[j] = min(dp[j], dp[j - v] + w)
            dp[j] = min(dp[j],dp[j+1])

    print((bisect.bisect_right(dp,W)-1))

if __name__ == "__main__":
    main()


# Optimized solution
import sys
import bisect


def input():
    return sys.stdin.readline().rstrip()


def main():
    N, W = list(map(int, input().split()))
    vsup = 10 ** 3 * N + 2
    dp = [10 ** 12 + 1] * (vsup)  # 価値の総和を i (以上にするための重さの最小値
    dp[0] = 0

    for i in range(N):
        w, v = list(map(int, input().split()))
        for j in range(vsup - 2, -1, -1):
            if j - v >= 0:
                dp[j] = min(dp[j], dp[j - v] + w, dp[j + 1])
            else:
                dp[j] = min(dp[j], dp[j + 1])

    print((bisect.bisect_right(dp, W) - 1))


if __name__ == "__main__":
    main()
# Original solution
from copy import deepcopy
n,W = list(map(int,input().split()))
dp = [10**12] * (10**5+1)
dp[0] = 0
for i in range(n):
  w,v = list(map(int,input().split()))
  pdp = deepcopy(dp)
  for j in range(v,10**5+1):
    dp[j] = min(pdp[j-v]+w,dp[j])
m = 0
for i in range(10**5+1):
  if dp[i] <= W:
    m = i
print(m)

# Optimized solution
n,W = list(map(int,input().split()))
dp = [[10**12] * (10**5+1) for i in range(n+1)]
dp[0][0] = 0
ma = 0
for i in range(1,n+1):
  w,v = list(map(int,input().split()))
  ma += v
  for j in range(v):
    dp[i][j] = dp[i-1][j]
  for j in range(v,ma+1):
    dp[i][j] = min(dp[i-1][j-v]+w,dp[i-1][j])
m = 0
for i in range(ma+1):
  if dp[-1][i] <= W:
    m = i
print(m)
# Original solution
N, W = list(map(int, input().split()))
goods = [list(map(int, input().split())) for i in range(N)]
v_sum = sum([i[1] 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][1]] + goods[i][0], dp[j])

for i in range(v_sum, -1, -1):
    if dp[i] <= W:
        print(i)
        break


# Optimized solution
N, W = list(map(int, input().split()))

items = [list(map(int, input().split())) for _ in range(N)]
v_sum = sum([item[1] for item in items])

inf = float("inf")
dp = [inf for _ in range(v_sum + 1)]

dp[0] = 0
for i in range(N):
    for j in range(v_sum, -1, -1):
        if dp[j] > dp[j - items[i][1]] + items[i][0]:
            dp[j] = dp[j - items[i][1]] + items[i][0]

for i in range(v_sum, -1, -1):
    if dp[i] <= W:
        print(i)
        exit()
# Original solution
N, W = list(map(int, input().split()))
items = [list(map(int, input().split())) for _ in range(N)]
sum_v = sum([item[1] for item in items])
inf = float("inf")
dp = [[inf for _ in range(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 - items[i][1] >= 0:
            dp[i+1][j] = min(dp[i][j], dp[i][j - items[i][1]] + items[i][0])
        else:
            dp[i+1][j] = dp[i][j]
for v in range(sum_v, -1, -1):
    if dp[N][v] <= W:
        print(v)
        exit()



# Optimized solution
N, W = list(map(int, input().split()))
items = [list(map(int, input().split())) for _ in range(N)]
sum_v = sum([item[1] for item in items])
inf = float("inf")
dp = [inf for _ in range(sum_v+1)]

dp[0] = 0
for i in range(N):
    for j in range(sum_v, -1, -1):
        if j - items[i][1] >= 0:
            dp[j] = min(dp[j], dp[j - items[i][1]] + items[i][0])

for v in range(sum_v, -1, -1):
    if dp[v] <= W:
        print(v)
        exit()
# Original solution

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
##############################


# https://qiita.com/drken/items/dc53c683d6de8aeacf5a#e-問題---knapsack-2


# N個の荷物、ナップザックの容量はW
N, W = list(map(int, input().split()))
w = [0] * N
v = [0] * N

for i in range(N):
    a, b = list(map(int, input().split()))
    w[i] = a
    v[i] = b

# 1 <= W <= 10^9なので横軸をWにするとテーブルがでかすぎる
# そのかわりにVの方を横軸にする


# 価値の総合計はまだ不明なので、適当にでかい値にしとく
# 最上部と最左部に0が入るので、その分を+1
V = 10**5
#dp = [ [0 for _ in range(W+1)] for _ in range(N+1) ]
dp = [ [float('inf') for _ in range(V+1)] for _ in range(N+1) ]

# 最小値を求めるので、上記でinfが入ってるので、初期値は0をいれる必要がある
dp[0][0] = 0

# dp[i][sum_v] = これまで(i-1)番目までの品物から価値がsum_v以上になるように選んだときの、重さの総和の最小値
for i in range(N):
    for sum_v in range(V):
        if sum_v - v[i] >= 0:
            dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v-v[i]]+w[i])

        dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v])


# 中身がWなので、W以下であるうちのsum_vの最大値を求めればいい
for sum_v in range(V):
    # 最終行だけ見ればいいので、端からsum_vの最大値をなめるだけ
    if dp[N][sum_v] <= W:
        ans = sum_v

print(ans)


# Optimized solution


# N個の荷物、ナップザックの容量はW
N, W = list(map(int, input().split()))
w = [0] * N
v = [0] * N

for i in range(N):
    a, b = list(map(int, input().split()))
    w[i] = a
    v[i] = b

# 1 <= W <= 10^9なので横軸をWにするとテーブルがでかすぎる
# そのかわりにVの方を横軸にする

# 価値の総合計はまだ不明なので、適当にでかい値にしとく
# 最上部と最左部に0が入るので、その分を+1
V = N*1000+1
dp = [ [float('inf') for _ in range(V+1)] for _ in range(N+1) ]

# 最小値を求めるので、上記でinfが入ってるので、初期値は0をいれる必要がある
dp[0][0] = 0

# dp[i][sum_v] = これまで(i-1)番目までの品物から価値がsum_v以上になるように選んだときの、重さの総和の最小値
for i in range(N):
    for sum_v in range(V):
        if sum_v - v[i] >= 0:
            dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v-v[i]]+w[i])

        dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v])


# 中身がWなので、W以下であるうちのsum_vの最大値を求めればいい
for sum_v in range(V):
    # 最終行だけ見ればいいので、端からsum_vの最大値をなめるだけ
    if dp[N][sum_v] <= W:
        ans = sum_v

print(ans)
# Original solution


# N個の荷物、ナップザックの容量はW
N, W = list(map(int, input().split()))
w = [0] * N
v = [0] * N

for i in range(N):
    a, b = list(map(int, input().split()))
    w[i] = a
    v[i] = b

# 1 <= W <= 10^9なので横軸をWにするとテーブルがでかすぎる
# そのかわりにVの方を横軸にする

# 価値の総合計はまだ不明なので、適当にでかい値にしとく
# 最上部と最左部に0が入るので、その分を+1
V = N*1000+1
dp = [ [float('inf') for _ in range(V+1)] for _ in range(N+1) ]

# 最小値を求めるので、上記でinfが入ってるので、初期値は0をいれる必要がある
dp[0][0] = 0

# dp[i][sum_v] = これまで(i-1)番目までの品物から価値がsum_v以上になるように選んだときの、重さの総和の最小値
for i in range(N):
    for sum_v in range(V):
        if sum_v - v[i] >= 0:
            dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v-v[i]]+w[i])

        dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v])


# 中身がWなので、W以下であるうちのsum_vの最大値を求めればいい
for sum_v in range(V):
    # 最終行だけ見ればいいので、端からsum_vの最大値をなめるだけ
    if dp[N][sum_v] <= W:
        ans = sum_v

print(ans)

# Optimized solution


import sys
input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
# A = [ int(input()) for _ in range(N) ]
##############################

N, W = list(map(int, input().split()))
w = []
v = []
for i in range(N):
    a, b = list(map(int, input().split()))
    w.append(a)
    v.append(b)

V = sum(v)

dp = [ [INF for _ in range(V+1)] for _ in range(N+1) ]

dp[0][0] = 0

for i in range(N):
    for j in range(V+1):
        if j - v[i] < 0:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = min(dp[i][j], dp[i][j-v[i]]+w[i])

#print(dp[N])

ans = 0
for v in range(V+1):
    if dp[N][v] <= W:
        ans = v

print(ans)
# Original solution
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,W=list(map(int,input().split()))
    WV=[tuple(map(int,input().split())) for _ in range(n)]

    V=100000
    dp=[INF]*(V+1)
    dp[0]=0

    for w,v in WV:
        for x in range(V,-1,-1):
            if(x+v<=V):
                dp[x+v]=min(dp[x+v],dp[x]+w)

    for x in range(V,-1,-1):
        if(dp[x]<=W):
            print(x)
            return
resolve()

# Optimized solution
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    n, W = list(map(int, input().split()))
    dp = [INF] * (n * 1001 + 1)
    dp[0] = 0
    for _ in range(n):
        w, v = list(map(int, input().split()))
        for v0 in range(n * 1001, -1, -1):
            if dp[v0] == INF:
                continue
            if v + v0 <= n * 1001:
                dp[v + v0] = min(dp[v + v0], dp[v0] + w)
    for v in range(n * 1001, -1, -1):
        if dp[v] <= W:
            print(v)
            return
resolve()
# Original solution
N,W = list(map(int,input().split(" ")))
INF =  1e11
v = [INF]*100010
v[0] = 0
for i in range(N):
  weight,value = list(map(int,input().split(" ")))
  for j in range(100001,0,-1):
    if j < value:
      break
    v[j] = min(v[j],v[j-value]+weight)

for i in range(100001,0,-1):
  if v[i] <= W:
    print(i)
    break



# Optimized solution
N,W = list(map(int,input().split(" ")))
INF =  1e11
v = [INF]*100010
v[0] = 0
for i in range(N):
  weight,value = list(map(int,input().split(" ")))
  for j in range(100001,0,-1):
    if j < value:
      break
    v[j] = min(v[j],v[j-value]+weight)

ans = 0
for i in range(100001,0,-1):
  if v[i] <= W:
    ans = i
    break
print(ans)
# Original solution
N, W = list(map(int, input().split()))

DP = dict()
DP[W] = 0

def maxv(i, v):
    if not DP.get(i):
        DP[i] = v
    else:
        if v > DP[i]:
            DP[i] = v

for w, v in (list(map(int, input().split())) for _ in range(N)):
    DPpre = DP.copy()
    for i in DPpre:
        if i - w >= 0:
            maxv(i-w, DPpre[i]+v)

print((max((DP[x] for x in DP))))


# Optimized solution
N, W = list(map(int, input().split()))

IN = list(list(map(int, input().split())) for _ in range(N))
sumw = 0
sumv = 0
for w, v in IN:
    sumw += w
    sumv += v

DP = dict()
DP[sumv] = sumw

def minv(i, v):
    if not DP.get(i):
        DP[i] = v
    else:
        if v < DP[i]:
            DP[i] = v

for w, v in IN:
    DPpre = DP.copy()
    for i in DPpre:
        minv(i-v, DPpre[i]-w)

for v in sorted(DP, reverse=True):
    if DP[v] <= W:
        print(v)
        break
# Original solution
N, W = list(map(int, input().split()))

IN = list(list(map(int, input().split())) for _ in range(N))
sumw = 0
sumv = 0
for w, v in IN:
    sumw += w
    sumv += v

DP = dict()
DP[sumv] = sumw

def minv(i, v):
    if not DP.get(i):
        DP[i] = v
    else:
        if v < DP[i]:
            DP[i] = v

if sumw <= W:
    ans = sumv
else:
    ans = 0
    for w, v in IN:
        DPpre = DP.copy()
        for i in DPpre:
            answ = i - v
            minv(answ, DPpre[i]-w)
            if answ > ans:
                if DP[answ] <= W:
                    ans = answ
                    continue

print(ans)


# Optimized solution
N, W = list(map(int, input().split()))

IN = list(list(map(int, input().split())) for _ in range(N))
sumw = 0
sumv = 0
for w, v in IN:
    sumw += w
    sumv += v

DP = dict()
DP[sumv] = sumw

def minv(i, v):
    if not DP.get(i):
        DP[i] = v
    else:
        if v < DP[i]:
            DP[i] = v

for w, v in IN:
    DPpre = DP.copy()
    for i in DPpre:
        minv(i-v, DPpre[i]-w)

for v in sorted(DP, reverse=True):
    if DP[v] <= W:
        print(v)
        break
# Original solution
N,W=list(map(int,input().split()))
lwv=[]
for i in range(N):
    lwv.append(list(map(int,input().split())))
ldp=[[float("inf") for j in range(10**5)] for i in range(N)]
for j in range(10**5):
    if lwv[0][1]>=j+1:
        ldp[0][j]=lwv[0][0]
for i in range(1,N):
    for j in range(10**5):
        comp=ldp[i-1][j+1-lwv[i][1]-1]+lwv[i][0] if j+1-lwv[i][1]>0 else lwv[i][0]
        ldp[i][j]=min(ldp[i-1][j],comp)
for j in range(10**5-1,-1,-1):
    if ldp[N-1][j]<=W:
        print((j+1))
        break


# Optimized solution
N,W=list(map(int,input().split()))
lw=[]
lv=[]
for i in range(N):
    w,v=list(map(int,input().split()))
    lw.append(w)
    lv.append(v)
ldp=[[float("inf") for j in range(10**5)] for i in range(N)]
for j in range(10**5):
    if lv[0]>=j+1:
        ldp[0][j]=lw[0]
for i in range(1,N):
    for j in range(10**5):
        ldp[i][j]=min(ldp[i-1][j],ldp[i-1][j+1-lv[i]-1]+lw[i] if j+1-lv[i]>0 else lw[i])
for j in range(10**5-1,-1,-1):
    if ldp[N-1][j]<=W:
        print((j+1))
        break
# Original solution
n,w=list(map(int, input().split()))
m=10**5+1
x=[list(map(int, input().split())) for i in range(n)]
dp=[[float('inf')]*m for i in range(n+1)]
dp[0][0]=0
for i in range(n):
    for j in range(m):
        if j>=x[i][1]:
            dp[i+1][j]=min(dp[i][j],dp[i][j-x[i][1]]+x[i][0])
        else:
            dp[i+1][j]=dp[i][j]
ans=0
for i in range(m):
    if dp[-1][i]<=w:ans=max(ans,i)
print(ans)

# Optimized solution
N, W = list(map(int, input().split()))
L = [list(map(int, input().split())) for i in range(N)]
V = 0
for i in range(N):
  V += L[i][1]

dp = [[float('inf')] * (V + 1) for i in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for j in range(V+1):
        if j - L[i][1] >= 0:
          dp[i+1][j] = min(dp[i][j], dp[i][j-L[i][1]] + L[i][0])
        else:
          dp[i+1][j] = dp[i][j]
ans = 0
for j in range(V+1):
    if  W >= dp[-1][j]:
        ans = max(ans, j)
print(ans)
# Original solution
N, W = list(map(int, input().split()))
L = [list(map(int, input().split())) for i in range(N)]
V = 0
for i in range(N):
  V += L[i][1]

dp = [[float('inf')] * (V + 1) for i in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for j in range(V+1):
        if j - L[i][1] >= 0:
          dp[i+1][j] = min(dp[i][j], dp[i][j-L[i][1]] + L[i][0])
        else:
          dp[i+1][j] = dp[i][j]
ans = 0
for j in range(V+1):
    if  W >= dp[-1][j]:
        ans = max(ans, j)
print(ans)

# Optimized solution
N, W = list(map(int, input().split()))
L = [list(map(int, input().split())) for i in range(N)]
V = 0
for i in range(N):
  V += L[i][1]

dp = [[10**9+1] * (V + 1) for i in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for j in range(V+1):
        if j - L[i][1] >= 0:
          dp[i+1][j] = min(dp[i][j], dp[i][j-L[i][1]] + L[i][0])
        else:
          dp[i+1][j] = dp[i][j]
ans = 0
for j in range(V+1):
    if  W >= dp[-1][j]:
        ans = max(ans, j)
print(ans)
# Original solution
N, W = list(map(int, input().split()))
L = [list(map(int, input().split())) for i in range(N)]
V = 0
for i in range(N):
  V += L[i][1]

dp = [[10**9+1] * (V + 1) for i in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for j in range(V+1):
        if j - L[i][1] >= 0:
          dp[i+1][j] = min(dp[i][j], dp[i][j-L[i][1]] + L[i][0])
        else:
          dp[i+1][j] = dp[i][j]
ans = 0
for j in range(V+1):
    if  W >= dp[-1][j]:
        ans = max(ans, j)
print(ans)

# Optimized solution
N, W = list(map(int, input().split()))
L = [list(map(int, input().split())) for i in range(N)]
V = 0
for i in range(N):
  V += L[i][1]

dp = [10**9+1] * (V + 1)
dp[0] = 0
for i in range(N):
    for j in range(V, -1, -1):
        dp[j] = min(dp[j], dp[j-L[i][1]] + L[i][0])
ans = 0
for j in range(V+1):
    if  W >= dp[j]:
        ans = max(ans, j)
print(ans)
# Original solution
N,W=list(map(int,input().split()))
w=[]
v=[]
for i in range(N):
    a,b=list(map(int,input().split()))
    w.append(a)
    v.append(b)
V=sum(v)

dp=[[float("inf") for i in range(V+1)] for _ in range(110)]
dp[0][0]=0

for i in range(0,N):
    for j in range(V+1):
        if j-v[i]>=0:
            dp[i+1][j]=min(dp[i+1][j],dp[i][j-v[i]]+w[i])

        dp[i+1][j]=min(dp[i+1][j],dp[i][j])


ans=0

for j in range(V+1):
    if dp[N][j]<=W:
        ans=j

print(ans)


# Optimized solution
N,W=list(map(int,input().split()))
w=[0]*N
v=[0]*N
for i in range(N):
    w[i],v[i]=list(map(int,input().split()))
V=sum(v)

dp=[[float("inf") ]*(V+1) for _ in range(110)]
dp[0][0]=0

for i in range(0,N):
    for j in range(V+1):
        if j-v[i]>=0:
            dp[i+1][j]=min(dp[i+1][j],dp[i][j-v[i]]+w[i])
        dp[i+1][j]=min(dp[i+1][j],dp[i][j])
ans=0
for j in range(V+1):
    if dp[N][j]<=W:
        ans=j
print(ans)
# Original solution
import sys
input = sys.stdin.readline

n, w = list(map(int, input().split()))
items = [tuple(map(int, input().split())) for _ in range(n)]

V_MAX = 10**5
dp = [[w + 1] * (V_MAX + 1) for _ in range(n + 1)]
dp[0][0] = 0

for i, (wi, vi) in enumerate(items):
    for j in range(V_MAX + 1):
        if j >= vi:
            dp[i + 1][j] = min(dp[i][j], dp[i][j - vi] + wi)
        else:
            dp[i + 1][j] = dp[i][j]

ans = 0
for i in range(n + 1):
    for j in range(V_MAX + 1):
        if dp[i][j] <= w:
            ans = max(ans, j)

print(ans)


# Optimized solution
import sys
input = sys.stdin.readline

n, w = list(map(int, input().split()))
items = [tuple(map(int, input().split())) for _ in range(n)]

V_MAX = 10**5
dp = [[w + 1] * (V_MAX + 1) for _ in range(n + 1)]
dp[0][0] = 0

for i, (wi, vi) in enumerate(items):
    for j in range(V_MAX + 1):
        if j >= vi:
            dp[i + 1][j] = min(dp[i][j], dp[i][j - vi] + wi)
        else:
            dp[i + 1][j] = dp[i][j]

ans = 0
for j in range(V_MAX + 1):
    if dp[n][j] <= w:
        ans = max(ans, j)

print(ans)
# Original solution
N,W = list(map(int, input().split()))
m = []
v = []
for i in range(N):
    a,b = list(map(int, input().split()))
    m.append(a)
    v.append(b)
sum_v = sum(v)
dp = [[float('inf') for i in range(sum_v+1001)]for j in range(N+1)]
for i in range(N):
    for j in range(sum_v+1):
        if j == 0:
            dp[i][j] = 0
        if j != float('inf'):
            dp[i+1][j+v[i]] = min(dp[i][j+v[i]],dp[i][j] + m[i])
            dp[i+1][j] = min(dp[i+1][j],dp[i][j])

for i in range(sum(v)+1):
    if  dp[-1][sum(v)-i] <= W:
        print((sum(v)-i))
        break


# Optimized solution
N,W = list(map(int, input().split()))
m = []
v = []
for i in range(N):
    a,b = list(map(int, input().split()))
    m.append(a)
    v.append(b)

sum_v = sum(v)
dp = [[10**15 for i in range(sum_v+1001)]for j in range(N+1)]
for i in range(N):
    dp[i][0] = 0
    for j in range(sum_v+1):
        if j != 10**15:
            dp[i+1][j+v[i]] = min(dp[i][j+v[i]],dp[i][j] + m[i])
            dp[i+1][j] = min(dp[i+1][j],dp[i][j])

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

V = sum(v)
# dp[i][j]:i番目までの品物から価値がj以上になるよう選んだときの重さの総和の最小値
dp = [[float("inf")] * (V + 1) for _ in range(N + 1)]

dp[0][0] = 0
for i in range(N):
	for j in range(V + 1):
		# i+1番目を選ぶ場合
		if j - v[i] >= 0:
			dp[i + 1][j] = min(dp[i + 1][j], dp[i][j - v[i]] + w[i])
		# i+1番目を選ばない場合
		dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])

# dp[N][j]がW以下であるようなjの最大値が答えになる
ans = 0
for j in range(V + 1):
	if dp[N][j] <= W:
		ans = j

print(ans)

# Optimized solution
N,W=list(map(int,input().split()))
w,v=[0]*N,[0]*N
for i in range(N):
    w[i],v[i]=list(map(int,input().split()))
dp=[[float('inf')]*(sum(v)+1) for i in range(N+1)]

dp[0][0]=0
for i in range(1,N+1):
    for j in range(len(dp[0])):
        if j>=v[i-1]:
            dp[i][j]=w[i-1]+dp[i-1][j-v[i-1]]
        dp[i][j]=min(dp[i][j],dp[i-1][j])

ans=0
for i in range(len(dp[0])):
    if dp[N][i]<=W:
        ans=i
print(ans)
# Original solution
n, w = list(map(int, input().split()))
wv = [tuple(map(int, input().split())) for _ in range(n)]

INF = 10**9 + 100
MAX_V = 10**5 + 100
dp = [INF] * (MAX_V + 1)
dp[0] = 0
for wi, vi in wv:
    for sum_v in reversed(list(range(vi, MAX_V+1))):
        dp[sum_v] = min(dp[sum_v - vi] + wi, dp[sum_v])
#print(dp)
ans = 0
for i in range(MAX_V, -1, -1):
    if dp[i] <= w:
        print(i)
        exit()
#print(ans)


# Optimized solution
n, w = list(map(int, input().split()))
wv = [tuple(map(int, input().split())) for _ in range(n)]

INF = 10**9 + 100
MAX_V = 10**5 + 100
dp = [INF] * (MAX_V + 1)
dp[0] = 0
for wi, vi in wv:
    for sum_v in reversed(list(range(vi, MAX_V+1))):
        dp[sum_v] = min(dp[sum_v - vi] + wi, dp[sum_v])
#print(dp)
ans = 0
for i in reversed(list(range(MAX_V+1))):
    if dp[i] <= w:
        print(i)
        exit()
#print(ans)
# Original solution
inf = float('inf')

n, w = list(map(int, input().split()))
wv = tuple(tuple(map(int, input().split())) for _ in range(n))

dp = tuple([inf] * (pow(10, 3) * n + 1) for _ in range(n + 1))
dp[0][0] = 0

for ind, (wi, vi) in enumerate(wv, 1):
    for v in range(pow(10, 3) * n + 1):
        if vi <= v:
            dp[ind][v] = min(dp[ind - 1][v], dp[ind - 1][v - vi] + wi)
        else:
            dp[ind][v] = dp[ind - 1][v]

for v in range(pow(10, 3) * n, 0, -1):
    if dp[n][v] <= w:
        print(v)
        exit()


# Optimized solution
inf = float('inf')

n, w = list(map(int, input().split()))
e = tuple(list(map(int, input().split())) for _ in range(n))
wt, vt = list(zip(*e))
sv = sum(vt)

dp = tuple([inf] * (sv + 1) for _ in range(n + 1))
dp[0][0] = 0

for i in range(n):
    dp[i + 1][:vt[i]] = dp[i][:vt[i]]
    for j in range(vt[i], sv + 1):
        dp[i + 1][j] = min(dp[i][j], dp[i][j - vt[i]] + wt[i])

res = -1
for j in range(sv, -1, -1):
    if dp[n][j] <= w:
        res = j
        break
print(res)
# Original solution
n,w=list(map(int,input().split()))
A=[list(map(int,input().split())) for i in range(n)]

dp=[float("inf")]*(10**5+1)
dp[0]=0
for i in range(n):
  for j in range(10**5,A[i][1]-1,-1):
    dp[j]=min(dp[j],dp[j-A[i][1]]+A[i][0])
ans=0
for v,e in enumerate(dp):
  if e<=w:
    ans=v
print(ans)

# Optimized solution
import sys
input=sys.stdin.readline
n,w=list(map(int,input().split()))
A=[list(map(int,input().split())) for i in range(n)]

dp=[float("inf")]*(10**5+1)
dp[0]=0
for i in range(n):
  for j in range(10**5,A[i][1]-1,-1):
    dp[j]=min(dp[j],dp[j-A[i][1]]+A[i][0])
ans=0
for v,e in enumerate(dp):
  if e<=w:
    ans=v
print(ans)