CodeEff/ECCO huggingface dataset:
# Original solution
#!/usr/bin/env python3
import sys
from collections.abc import Iterable
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    dp = [[float('inf')] * (N * 1000 + 1) for _ in range(N+1)]
    dp[0][0] = 0

    for i, (cw, cv) in enumerate(zip(w, v)):
        for j in range(N * 1000 + 1):
            dp[i+1][j] = dp[i][j]
            if 0 <= (j - cv) and (dp[i][j - cv] + cw) <= W:
                dp[i+1][j] = min(dp[i+1][j], dp[i][j - cv] +  cw)

    return max([cv for cv, cw in enumerate(dp[-1]) if isfinite(cw)])


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    w = [int()] * (N)  # type: "List[int]" 
    v = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    result = solve(N, W, w, v)
    if isinstance(result, Iterable) and not isinstance(result, str):
        result = '\n'.join([str(v) for v in result])
    print(result)

if __name__ == '__main__':
    main()


# Optimized solution
#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    dp = [[float('inf')] * (N * 1000 + 1) for _ in range(N+1)]
    dp[0][0] = 0

    for i, (cw, cv) in enumerate(zip(w, v)):
        for j in range(N * 1000 + 1):
            dp[i+1][j] = dp[i][j]
            if 0 <= (j - cv) and (dp[i][j - cv] + cw) <= W:
                dp[i+1][j] = min(dp[i+1][j], dp[i][j - cv] +  cw)

    return max([cv for cv, cw in enumerate(dp[-1]) if isfinite(cw)])


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    w = [int()] * (N)  # type: "List[int]"
    v = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    result = solve(N, W, w, v)
    print(result)

if __name__ == '__main__':
    main()
# Original solution
N, W = list(map(int, input().split()))
w_v = [list(map(int, input().split())) for _ in range(N)]

V = max(w_v, key=lambda x: x[1])[1] * N
# 1~i-1番目の品物から価値の総和がj以下になるように選んだときの重さ
dp = [[float('inf') for _ in range(V+1)] for _ in range(N+1)]
dp[0][0] = 0

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

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

# Optimized solution
n, W = list(map(int, input().split()))
data = []
for _ in range(n):
    w, v = list(map(int, input().split()))
    data.append((w, v))

V = sum([v for _, v in data])
dp = [[float("inf")] * (V + 1) for i in range(n + 1)]
dp[0][0]= 0

for i in range(1, n+1):
    w, v = data[i-1]
    for j in range(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]

print((max([i for i, x in enumerate(dp[-1]) if x != "inf" and x <= W])))
# Original solution
N, M = list(map(int, input().split()))
L = 1000000
dp = [[10000000010 for _ in range(L+1)] for _ in range(N+1)]
W, V = [], []
for _ in range(N):
    w, v = list(map(int, input().split()))
    W.append(w)
    V.append(v)
dp[0][0] = 0
for i in range(N):
    for j in range(L):
        if j + V[i] <= L:
            dp[i+1][j] = min(dp[i][j], dp[i][j-V[i]] + W[i])
        else:
            dp[i+1][j] = dp[i][j]
for i, d in enumerate(dp[N]):
    if d <= M:
        maxv = i
print(maxv)

# Optimized solution
N, M = list(map(int, input().split()))
L = 100000
dp = [[1000000001 for _ in range(L+1)] for _ in range(N+1)]
W, V = [], []
for _ in range(N):
    w, v = list(map(int, input().split()))
    W.append(w)
    V.append(v)
dp[0][0] = 0
for i in range(N):
    for j in range(L+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]
for i, d in enumerate(dp[N]):
    if d <= M:
        maxv = i
print(maxv)
# Original solution
"""
重さと価値がそれぞれw_i,v_iであるようなn個の品物がある.
これらの品物の中から, 重さの総和がWを超えないように選んだ時の,
価値の総和の最大値を求めよ.
1<=n<=100, 1<=w_i<=10^7, 1<=v_i<=100, 1<=W<=10^9
"""
#-------------------------------------------------------------------------------

#入力
INF = 2000000000
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 = [[INF for i in range(V + 1)] for j in range(n + 1)]

#ここからメイン
dp[0][0] = 0
for i in range(n):
    for j in range(V + 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])
ans = 0
for i in range(V + 1):
    if dp[n][i] <= W:
        ans = i
print(ans)


# Optimized solution
"""
重さと価値がそれぞれw_i,v_iであるようなn個の品物がある.
これらの品物の中から, 重さの総和がWを超えないように選んだ時の,
価値の総和の最大値を求めよ.
1<=n<=100, 1<=w_i<=10^7, 1<=v_i<=100, 1<=limit_w<=10^9
"""
#-------------------------------------------------------------------------------

#入力
INF = 2000000000
"""
メモ : Pythonでは無限大を表す float('inf') があるが, 処理がかなり重たいので
       代わりにsum(v)より真に大きい 2*10^9 を INFとする.
       (https://atcoder.jp/contests/dp/tasks/dp_e において,PyPyを使用して,
        前者だと1060ms, 後者だと570msで2倍近く差が出ている.)
"""
n ,limit_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()))
sum_v = sum(v)
dp = [[INF for i in range(sum_v + 1)] for j in range(n + 1)] 
# dp[i][j]には重さが入る.
# dp[i][j]=(i番目までの品物から価値がちょうどｊになるための重さの最小値)

# ここからメイン
dp[0][0] = 0
for i in range(n):
    for j in range(sum_v + 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])
            
# n個まで使って,重さがlimit_wを超えないで価値が最大のものを求める.
ans = 0
for i in range(sum_v + 1):
    if dp[n][i] <= limit_w:
        ans = i
print(ans)
# Original solution
"""
重さと価値がそれぞれw_i,v_iであるようなn個の品物がある.
これらの品物の中から, 重さの総和がWを超えないように選んだ時の,
価値の総和の最大値を求めよ.
1<=n<=100, 1<=w_i<=10^7, 1<=v_i<=100, 1<=limit_w<=10^9
"""
#-------------------------------------------------------------------------------

#入力
INF = 2000000000
"""
メモ : Pythonでは無限大を表す float('inf') があるが, 処理がかなり重たいので
       代わりにsum(v)より真に大きい 2*10^9 を INFとする.
       (https://atcoder.jp/contests/dp/tasks/dp_e において,PyPyを使用して,
        前者だと1060ms, 後者だと570msで2倍近く差が出ている.)
"""
n ,limit_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()))
sum_v = sum(v)
dp = [[INF for i in range(sum_v + 1)] for j in range(n + 1)] 
# dp[i][j]には重さが入る.
# dp[i][j]=(i番目までの品物から価値がちょうどｊになるための重さの最小値)

# ここからメイン
dp[0][0] = 0
for i in range(n):
    for j in range(sum_v + 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])
            
# n個まで使って,重さがlimit_wを超えないで価値が最大のものを求める.
ans = 0
for i in range(sum_v + 1):
    if dp[n][i] <= limit_w:
        ans = i
print(ans)


# Optimized solution
"""
重さと価値がそれぞれw_i,v_iであるようなn個の品物がある.
これらの品物の中から, 重さの総和がWを超えないように選んだ時の,
価値の総和の最大値を求めよ.
1<=n<=100, 1<=w_i<=10^7, 1<=v_i<=100, 1<=limit_w<=10^9
"""
#-------------------------------------------------------------------------------

#入力
INF = 2000000000
"""
メモ : Pythonでは無限大を表す float('inf') があるが, 処理がかなり重たいので
       代わりにsum(v)より真に大きい 2*10^9 を INFとする.
       (https://atcoder.jp/contests/dp/tasks/dp_e において,PyPyを使用して,
        前者だと1060ms, 後者だと570msで2倍近く差が出ている.)
"""
n ,limit_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()))
sum_v = sum(v)
dp = [INF for i in range(sum_v + 1)]
# dp[i][j]には重さが入る.
# dp[i][j]=(i番目までの品物から価値がちょうどｊになるための重さの最小値)

# ここからメイン
dp[0] = 0
for i in range(n):
    for j in range(sum_v ,-1,-1):
        if j >= v[i]:
            dp[j] = min(dp[j], dp[j - v[i]] + w[i])

# n個まで使って,重さがlimit_wを超えないで価値が最大のものを求める.
ans = 0
for i in range(sum_v + 1):
    if dp[i] <= limit_w:
        ans = i
print(ans)
# Original solution
n, w = list(map(int, input().split()))
item = [list(map(int, input().split())) for i in range(n)]

max_v = 100005

dp = [[float('inf') for i in range(max_v)] for j in range(n + 1)]

dp[0][0] = 0
for i in range(n):
    for sum_v in range(max_v):
        if sum_v - item[i][1] >= 0:
            dp[i + 1][sum_v] = min(dp[i + 1][sum_v], dp[i][sum_v - item[i][1]] + item[i][0])
        dp[i + 1][sum_v] = min((dp[i + 1][sum_v], dp[i][sum_v]))

ans = 0
for sum_v in reversed(list(range(max_v))):
    if dp[-1][sum_v] <= w:
        print(sum_v)
        break

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

max_v = 100005

dp = [[float('inf')] * max_v for j in range(n + 1)]
dp[0][0] = 0

for i in range(n):
    for sum_v in range(max_v):
        if sum_v - item[i][1] >= 0:
            dp[i + 1][sum_v] = min(dp[i + 1][sum_v], dp[i][sum_v - item[i][1]] + item[i][0])
        dp[i + 1][sum_v] = min((dp[i + 1][sum_v], dp[i][sum_v]))

for sum_v in reversed(list(range(max_v))):
    if dp[-1][sum_v] <= w:
        print(sum_v)
        break
# Original solution
N, W = list(map(int, input().split()))
table = []
for i in range(N):
  w,v = list(map(int, input().split()))
  table.append((w,v))
INF = W+1
dp = [[INF]*(10**3*N+1) for i in range(N+1)]
dp[0][0] = 0
for i in range(1,N+1):
  for k in range(10**3*N+1):
    w,v = table[i-1]
    dp[i][k] = dp[i-1][k]
    if v<=k and dp[i-1][k-v] <= INF:
      dp[i][k] = min(dp[i][k],dp[i-1][k-v]+w)

for i in range(10**3*N,-1,-1):
  if 0<= dp[-1][i] <= W:
    print(i)
    exit()


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

N, W = list(map(int, input().split()))
table = []
for i in range(N):
  w,v = list(map(int, input().split()))
  table.append((w,v))
INF = W+1
dp = [[INF]*(10**3*N+1) for i in range(N+1)]
dp[0][0] = 0
for i in range(1,N+1):
  for k in range(10**3*N+1):
    w,v = table[i-1]
    dp[i][k] = dp[i-1][k]
    if v<=k and dp[i-1][k-v] <= INF:
      dp[i][k] = min(dp[i][k],dp[i-1][k-v]+w)

for i in range(10**3*N,-1,-1):
  if 0<= dp[-1][i] <= W:
    print(i)
    exit()
# Original solution
import sys
input = sys.stdin.readline

N, W = list(map(int, input().split()))
table = []
for i in range(N):
  w,v = list(map(int, input().split()))
  table.append((w,v))
INF = W+1
dp = [[INF]*(10**3*N+1) for i in range(N+1)]
dp[0][0] = 0
for i in range(1,N+1):
  for k in range(10**3*N+1):
    w,v = table[i-1]
    dp[i][k] = dp[i-1][k]
    if v<=k and dp[i-1][k-v] <= INF:
      dp[i][k] = min(dp[i][k],dp[i-1][k-v]+w)

for i in range(10**3*N,-1,-1):
  if 0<= dp[-1][i] <= W:
    print(i)
    exit()


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

N, W = list(map(int, input().split()))
table = []
for i in range(N):
  w,v = list(map(int, input().split()))
  table.append((w,v))
dp = [[W+1]*(10**3*N+1) for i in range(N+1)]
dp[0][0] = 0

for i in range(1,N+1):
  w,v = table[i-1]
  for j in range(10**3*N+1):
    dp[i][j] = dp[i-1][j]
    if j>=v:
      dp[i][j] = min(dp[i][j],dp[i-1][j-v]+w)

for i in range(10**3*N,-1,-1):
  if dp[-1][i] <= W:
    print(i)
    exit()
# Original solution
n=0
W=0
n,W=list(map(int,input().split()))
dp=[W+1]*(101010)
dp[0]=0
for i in range(n):
    w,v=list(map(int,input().split()))
    j=100000
    while j>=0:
        if dp[j+v]>dp[j]+w:
            dp[j+v]=dp[j]+w
        j-=1
ans=0
for v in range(len(dp)):
    if dp[v]<=W:
        ans=v
print(ans)

# Optimized solution
n=0
W=0
n,W=list(map(int,input().split()))
dp=[W+1]*101010
dp[0]=0
for i in range(n):
    w,v=list(map(int,input().split()))
    j=100000
    while j>=0:
        if dp[j+v]>dp[j]+w:
            dp[j+v]=dp[j]+w
        j-=1
ans=0
for v in range(len(dp)):
    if dp[v]<=W:
        ans=v
print(ans)
# Original solution
def recur(n,w):
    if n==0 or w==0:
        return 0
    elif (n,w) in dp:
        return dp[(n,w)]
    elif l[n-1][0]<=w:
        k=max(recur(n-1,w-l[n-1][0])+l[n-1][1],recur(n-1,w))
        dp[(n,w)]=k
        return k
    else:
        k=recur(n-1,w)
        dp[(n,w)]=k
        return k
n,w=list(map(int,input().split()))
l=[]
for _ in range(n):
    a,b=list(map(int,input().split()))
    l.append((a,b))
dp=dict()
print((recur(n,w)))
    

# Optimized solution
n,w=list(map(int,input().split()))
l=[]
weight=[0]
value=[0]

for _ in range(n):
    a,b=list(map(int,input().split()))
    value.append(b)
    weight.append(a)
maxvalue=sum(value)
dp=[[10**10 for i in range(maxvalue+1)]for i in range(n+1)]
for i in range(n+1):
    dp[i][0]=0
for i in range(1,n+1):
    for j in range(1,maxvalue+1):
        if value[i]<=j:
            
            dp[i][j]=min(dp[i-1][j],dp[i-1][j-value[i]]+weight[i])
        else:
            dp[i][j]=dp[i-1][j]
for i in range(maxvalue+1):
    if dp[-1][i]<=w:
        ans=i
print(ans)
# Original solution
def main():
    n, m = 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()))
    t = sum(v) + 1
    l = [m + 1] * (t + 1) 
    for i in range(n):
        for j in range(t, v[i] - 1, -1):
            k = l[j - v[i]] + w[i]
            if j == v[i] and w[i] < l[j]:
                l[j] = w[i]
            elif k < l[j]:
                l[j] = k
    for i in range(t, 0, -1):
        if l[i] <= m:
            print(i)
            break
main()


# Optimized solution
def main():
    n, m = 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()))
    t = sum(v)
    l = [m + 1] * (t + 1)
    l[0] = 0
    for i in range(n):
        for j in range(t, v[i] - 1, -1):
            k = l[j - v[i]] + w[i]
            if k < l[j]:
                l[j] = k
    for i in range(t, 0, -1):
        if l[i] <= m:
            print(i)
            break
main()
# Original solution
# -*- coding: utf-8 -*-
v_max = 100010
INF = 1000000100
n, w = list(map(int, input().split()))
weight = [0]*n
value = [0]*n
dp = [[INF for i in range(v_max+1)] for i in range(n+1)]
dp[0][0] = 0

for i in range(n):
    weight[i], value[i] = list(map(int, input().split()))

for i in range(n):
    for j in range(v_max+1):
        if j - value[i] >= 0:
            dp[i+1][j] = min(dp[i+1][j], dp[i][j - value[i]] + weight[i])
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])

result = 0
for j in range(v_max+1):
    # print("v_sum: " + str(j) + " , weight: " + str(dp[n][j]))
    if dp[n][j] <= w:
        result = j
print(result)


# Optimized solution
# -*- coding: utf-8 -*-
v_max = 100010
INF = 1000000100
n, w = list(map(int, input().split()))
weight = [0]*n
value = [0]*n
dp = [[INF for i in range(v_max+1)] for i in range(n+1)]
dp[0][0] = 0

for i in range(n):
    weight[i], value[i] = list(map(int, input().split()))

for i in range(n):
    for j in range(v_max+1):
        if j - value[i] >= 0:
            dp[i+1][j] = min(dp[i+1][j], dp[i][j - value[i]] + weight[i])
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])

result = 0
for j in range(v_max+1):
    if dp[n][j] <= w:
        result = j
print(result)
# Original solution
def main():
  n, w = [int(e) for e in input().split()]
  maxv = 10 ** 3 * n + 1
  t = [-1 for i in range(maxv)]
  t[0] = w
  for _ in range(n):
    nw, nv = [int(e) for e in input().split()]
    for i in range(maxv - 1, -1, -1):
      if t[i] == -1:
        continue
      if t[i + nv] < t[i] - nw:
        t[i + nv] = t[i] - nw
  for i in range(maxv - 1, 0, -1):
    if t[i] == -1:
      continue
    print(i)
    break
main()

# Optimized solution
def main():
  n, w = [int(e) for e in input().split()]
  maxv = 10 ** 3 * n + 1
  t = [-1 for i in range(maxv)]
  t[0] = w
  cmaxv = 0
  for _ in range(n):
    nw, nv = [int(e) for e in input().split()]
    for i in range(cmaxv, -1, -1):
      if t[i] == -1:
        continue
      if t[i + nv] < t[i] - nw:
        t[i + nv] = t[i] - nw
        if cmaxv < i + nv:
          cmaxv = i + nv
  print(cmaxv)
main()
# Original solution
def main():
  n, w = [int(e) for e in input().split()]
  maxv = 10 ** 3 * n + 1
  t = [-1 for i in range(maxv)]
  t[0] = w
  cmaxv = 0
  for _ in range(n):
    nw, nv = [int(e) for e in input().split()]
    for i in range(cmaxv, -1, -1):
      if t[i] == -1:
        continue
      if t[i + nv] < t[i] - nw:
        t[i + nv] = t[i] - nw
        if cmaxv < i + nv:
          cmaxv = i + nv
  print(cmaxv)
main()

# Optimized solution
from sys import stdin
def main():
  from builtins import int, range
  readline = stdin.readline
  n, w = list(map(int, readline().split()))
  maxv = 10 ** 3 * n + 1
  t = [-1] * maxv
  t[0] = w
  cmaxv = 0
  for _ in range(n):
    nw, nv = list(map(int, readline().split()))
    for i in range(cmaxv, -1, -1):
      ti = t[i]
      if ti == -1:
        continue
      if t[i + nv] < ti - nw:
        t[i + nv] = ti - nw
        if cmaxv < i + nv:
          cmaxv = i + nv
  print(cmaxv)
main()
# Original solution
def dp_fn():
  N, W = list(map(int, input().split()))
  WV = (list(map(int, input().split())) for _ in range(N))
  
  DP = {0:0}
  
  for w, v in WV:
    keys = sorted(list(DP.keys()), reverse=True)
    for i in keys:
      if i + w <= W:
        if i+w in DP:
          DP[i+w] = max(DP[i] + v, DP[i+w])
        else:
          DP[i+w] = DP[i] + v
  return max(DP.values())
  
print((dp_fn()))


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

def dp_fn():
  N, W = list(map(int, input().split()))
  WV = (list(map(int, input().split())) for _ in range(N))
  
  DP = {0:0}
  
  for w, v in WV:
    keys = sorted(list(DP.keys()), reverse=True)
    for i in keys:
      j = DP[i]
      if j+w <= W:
        if i+v in DP:
          DP[i+v] = min(DP[i+v], j+w)
        else:
          DP[i+v] = j+w
  return max(DP.keys())
  
print((dp_fn()))
# Original solution
n,w = list(map(int, input().split()))
wv = []
vsum=0
for _ in range(n):
    tmp = list(map(int,input().split()))
    wv.append(tmp)
    vsum += tmp[1]

dp = [[float("inf") for i in range(vsum+1)] for j in range(n+1)]
dp[0][0]=0

for i in range(1,n+1):
    now_w,now_v =wv[i-1]
    for v in range(vsum+1):
        dp[i][v] = dp[i-1][v]
        if v - now_v >= 0:
            dp[i][v] = min(dp[i][v],dp[i-1][v-now_v] + now_w)

ans=0
for val in range(len(dp[-1])):
    if dp[-1][val] <= w:
        ans=val
print(ans)

# Optimized solution
n,w = list(map(int, input().split()))
wv = []
vsum=0
for _ in range(n):
    tmp = list(map(int,input().split()))
    wv.append(tmp)
    vsum += tmp[1]

INF = 1 << 30

dp = [[INF for i in range(vsum+1)] for j in range(n+1)]
dp[0][0]=0

for i in range(1,n+1):
    now_w,now_v =wv[i-1]
    for v in range(vsum+1):
        dp[i][v] = dp[i-1][v]
        if v - now_v >= 0:
            dp[i][v] = min(dp[i][v],dp[i-1][v-now_v] + now_w)

ans=0
for val in range(len(dp[-1])):
    if dp[-1][val] <= w:
        ans=val
print(ans)
# Original solution
n,mw=list(map(int,input().split()))
l=[list(map(int,input().split())) for _ in range(n)]
dp=[[float('inf') for _ in range(10**5+10)]for _ in range(n+1)]
#dp[i][j]=i個目までの品物を選んだとき、価値をjにする最小の重さ
dp[0][0]=0
for i in range(n):
    w,v=l[i]
    for j in range(10**5+10):
        dp[i+1][j]=min(dp[i+1][j],dp[i][j])
        if j+v<10**5+10:
            dp[i+1][j+v]=min(dp[i+1][j+v],dp[i][j]+w)
    for j in range(10**5+9):
        dp[i+1][-2-j]=min(dp[i+1][-2-j],dp[i+1][-1-j])
for i in range(10**5+10):
    if dp[-1][i]>mw:
        print((i-1))
        break

# Optimized solution
n,W=list(map(int,input().split()))
a=[list(map(int,input().split())) for _ in range(n)]
m=sum([a[i][1] for i in range(n)])
dp=[[float('inf') for _ in range(m+1)] for _ in range(n+1)]
dp[0][0]=0
for i in range(n):
    weight,value=a[i]
    for j in range(m+1):
        dp[i+1][j]=min(dp[i][j],dp[i+1][j])
        if j+value<=m:
            dp[i+1][j+value]=min(dp[i][j+value],dp[i][j]+weight)
for i in range(m+1):
    if dp[-1][-i-1]<=W:
        print((m-i))
        break
# Original solution
import sys
import math
from collections import deque
import copy
INF = float("inf")
N, W = list(map(int, input().split()))
weight = []
value = []
for i in range(N):
    tempW, tempV = list(map(int, input().split()))
    weight.append(tempW)
    value.append(tempV)

dp = [[INF for _ in range(N * 1000 + 1)] for _ in range(N + 1)]
dp[0][0] = 0

for i in range(1, N + 1):
    for l in range(N * 1000 + 1):
        if l - value[i - 1] >= 0:
            dp[i][l] = min(dp[i - 1][l], dp[i - 1][l - value[i - 1]] + weight[i - 1])
        else:
            dp[i][l] = dp[i - 1][l]
for i in range(N * 1000 + 1):
    if dp[N][i] <= W:
        ans = i
print(ans)


# Optimized solution
import sys
import math
from collections import deque
import copy
input = sys.stdin.readline
INF = 10**9+7
N, W = list(map(int, input().split()))
weight = []
value = []
for i in range(N):
    tempW, tempV = list(map(int, input().split()))
    weight.append(tempW)
    value.append(tempV)

dp = [[INF for _ in range(N * 1000 + 1)] for _ in range(N + 1)]
dp[0][0] = 0

for i in range(1, N + 1):
    for l in range(N * 1000 + 1):
        if l - value[i - 1] >= 0:
            dp[i][l] = min(dp[i - 1][l], dp[i - 1][l - value[i - 1]] + weight[i - 1])
        else:
            dp[i][l] = dp[i - 1][l]
for i in range(N * 1000 + 1):
    if dp[N][i] <= W:
        ans = i
print(ans)
# Original solution
N,W = list(map(int,input().split()))
INF = 10**12
V = 1000 * N
Data = []
Data.append([0,0])
for _ in range(N):
    Data.append(list(map(int,input().split())))

#DP[n][v]: n番目までの品物で 価値vの品物を選んだ場合の重さの最小
DP = [[INF]*(V+1) for _ in range(N+1)]
for n in range(N+1):
    DP[n][0] = 0

for n in range(1,N+1):
    for v in range(1,V+1):
        wi,vi = Data[n]
        if v >= vi:
            DP[n][v] = min(DP[n][v],DP[n-1][v-vi]+wi)
        DP[n][v] = min(DP[n][v],DP[n-1][v])

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

# Optimized solution
N,W = list(map(int,input().split()))
INF = 10**12
V = 1000 * N
Data = []
Data.append([0,0])
for _ in range(N):
    Data.append(list(map(int,input().split())))

DP = [[INF]*(V+1) for _ in range(N+1)]
for n in range(N+1):
    DP[n][0] = 0

for n in range(1,N+1):
    for v in range(1,V+1):
        wi,vi = Data[n]
        if v >= vi:
            DP[n][v] = min(DP[n][v],DP[n-1][v-vi]+wi)
        DP[n][v] = min(DP[n][v],DP[n-1][v])

ans = 0
for  v in range(V+1):
    if DP[N][v] <= W:
        ans = v
print(ans)
# Original solution
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from math import *
from itertools import *
from copy import *

N, W = list(map(int, input().split()))
MV = N * 10**3 + 1
INF = float('inf')
dp1 = [INF] * MV
dp1[0] = 0
for i in range(N):
    dp2 = [INF] * MV
    w, v = list(map(int, input().split()))
    for j in range(MV):
        dp2[j] = min(dp1[j], dp1[j-v]+w)
    dp1 = deepcopy(dp2)
for i in range(MV-1, -1, -1):
    if dp1[i] <= W:
        print(i)
        break


# Optimized solution
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from math import *
from itertools import *
from copy import *

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