Problem:
 Score : 100 points    Problem Statement There are N items, numbered 1, 2, \ldots, N .
For each i ( 1 \leq i \leq N ), Item i has a weight of w_i and a value of v_i .  Taro has decided to choose some of the N items and carry them home in a knapsack.
The capacity of the knapsack is W , which means that the sum of the weights of items taken must be at most W .  Find the maximum possible sum of the values of items that Taro takes home.      Constraints  All values in input are integers.  1 \leq N \leq 100  1 \leq W \leq 10^9  1 \leq w_i \leq W  1 \leq v_i \leq 10^3         Input Input is given from Standard Input in the following format:  N  W  w_1  v_1  w_2  v_2  :  w_N  v_N       Output Print the maximum possible sum of the values of items that Taro takes home.        Sample Input 1 3 8
3 30
4 50
5 60      Sample Output 1 90  Items 1 and 3 should be taken.
Then, the sum of the weights is 3 + 5 = 8 , and the sum of the values is 30 + 60 = 90 .       Sample Input 2 1 1000000000
1000000000 10      Sample Output 2 10       Sample Input 3 6 15
6 5
5 6
6 4
6 6
3 5
7 2      Sample Output 3 17  Items 2, 4 and 5 should be taken.
Then, the sum of the weights is 5 + 6 + 3 = 14 , and the sum of the values is 6 + 6 + 5 = 17 .

Solution (Python):

import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


class PriorityQueue:
    def __init__(self, l=[]):
        self.__q = l
        heapq.heapify(self.__q)
        return

    def push(self, n):
        heapq.heappush(self.__q, n)
        return

    def pop(self):
        return heapq.heappop(self.__q)


MOD = int(1e09) + 7
INF = int(1e15)

V_MAX = int(1e05)+1


def main():
    
    N, W = Scanner.map_int()
    V = [Scanner.map_int() for i in range(N)]
    dp = [[INF for _ in range(V_MAX)] for _ in range(N+1)]
    dp[0][0] = 0

    for i in range(N):
        for j in range(V_MAX):
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
            dp[i+1][j] = min(dp[i+1][j], dp[i][j - V[i][1]] + V[i][0])
    ans = 0
    for i in range(V_MAX):
        if dp[N][i] <= W:
            ans = i
    print(ans)
    return


if __name__ == "__main__":
    main()

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


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

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

ans=0

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

print(ans)

Solution (Python):
def solve():
    n, w = map(int, input().split())
    l = [list(map(int, input().split())) for i in range(n)]

    lim = n * 10 ** 3 + 1
    dp = [[10**15 for i in range(lim)] for i in range(n+1)]

    for i in range(n+1):
        dp[i][0] = 0

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

    ans = 0
    for sum_v in range(lim):
        if dp[n][sum_v] <= w:
            ans = sum_v

    print(ans)

if __name__ == '__main__':
    solve()

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

Solution (Python):
n,w=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]

lim=n*10**3+1

dp=[[10**15 for i in range(lim)] for i in range(n+1)]

for i in range(n+1):
 dp[i][0]=0



for i in range(n):
 for sum_v in range(lim):

  if sum_v-l[i][1]>=0:
   dp[i+1][sum_v] = min(dp[i+1][sum_v],dp[i][sum_v-l[i][1]]+l[i][0])

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

ans=0
for i in range(lim):
 if dp[-1][i]<=w:
  ans=max(ans,i)
print(ans)

Solution (Python):
n,w=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]

lim=n*10**3+1

dp=[[10**15 for i in range(lim)] for i in range(n+1)]

'''
for i in range(n+1):
 dp[i][0]=0
'''
dp[0][0]=0

for i in range(n):
 for sum_v in range(lim):

  if sum_v-l[i][1]>=0:
   dp[i+1][sum_v] = min(dp[i+1][sum_v],dp[i][sum_v-l[i][1]]+l[i][0])

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

ans=0
for i in range(lim):
 if dp[-1][i]<=w:
  ans=max(ans,i)
print(ans)

Solution (Python):
N, W = map(int, input().split())

wv = []
for i in range(N):
    wv.append(list(map(int, input().split())))
    
dp = [[10**15 for i in range(10**5+1)] for j in range(N+1)]
dp[0][0] = 0

for i in range(N):
    for sum_v in range(10**5+1):
        if sum_v - wv[i][1] >= 0:
            dp[i+1][sum_v] = min(dp[i][sum_v - wv[i][1]] + wv[i][0], dp[i][sum_v])
        else:
            dp[i+1][sum_v] = dp[i][sum_v]

ans = 0
for sum_v in range(10**5+1):
    if dp[N][sum_v] <= W:
        ans = sum_v

print(ans)

Solution (Python):
N,W  = map(int,input().split())
w = []
v = []
for i in range(N):
    a,b = map(int,input().split())
    w.append(a)
    v.append(b)
BIG = 10**15+1
LEN = 10**3
LEN = LEN*N
dp = [[BIG for i in range(LEN+1)]for j in range(N+1)]
for i in range(N+1):
    dp[i][0] = 0

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

ans = 0
for j in range(LEN+1):
    if dp[N][j] <= W and j >= ans:
        ans = j

        
print(ans)

Solution (Python):
n,w=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)

Solution (Python):
import sys
input=sys.stdin.readline
n,w=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)

Solution (Python):
N,W = list(map(int,input().split()))
w = [0]*N
v = [0]*N

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

inf = float("inf")
dp = [[inf]*(v_max+1) for i in range(N)]
dp[0][v[0]] = w[0]
for i in range(N):
	dp[i][0] = 0

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

ans = 0
for v_temp in range(v_max+1):
	if dp[N-1][v_temp] <= W:
		ans = v_temp

print(ans)

Solution (Python):
N, W = list(map(lambda x: int(x), input().split()))
w = []
v = []
for i in range(N):
  line = input().split()
  w.append(int(line[0]))
  v.append(int(line[1]))
  
inf = 10**10
M = sum(v)+1
dp = [ [0] + [inf]*(M-1) for i in range(N) ]
dp[0][v[0]] = w[0] 

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

for val in reversed(range(M)):
  if dp[N-1][val]<=W:
    print(val)
    break

Solution (Python):
N, W = list(map(lambda x: int(x), input().split()))
w = []
v = []
for i in range(N):
  line = input().split()
  w.append(int(line[0]))
  v.append(int(line[1]))
  
inf = 10**10
M = sum(v)+1
dp = [ [0] + [inf]*(M-1) for i in range(N) ]
dp[0][v[0]] = w[0] 

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

for val in reversed(range(M)):
  if dp[N-1][val]<=W:
    print(val)
    break

Solution (Python):
INF = 10**10 - 1


N,Wmax = map(int, input().split())
w = [0]*(N+1)
v = [0]*(N+1)
Vsum = 0
for i in range(1,N+1):
    w[i],v[i] = map(int, input().split())
    Vsum += v[i]


dp = [[INF] * (Vsum+1) for i in range(N+1)]
for i in range(0,N+1):
    dp[i][0] = 0


for i in range(1,N+1):
    for vv in range(1,Vsum+1):
        if v[i] > vv:
            dp[i][vv] = dp[i-1][vv]
        else:
            dp[i][vv] = min(dp[i-1][vv],dp[i-1][vv-v[i]]+w[i])
    

Vmax = 0
for vv in range(1,Vsum+1):
    if dp[N][vv] <= Wmax:
        Vmax = vv
print(Vmax)

Solution (Python):
n, w = map(int, input().split())
x = [list(map(int, input().split())) for _ in range(n)]

v = sum([vi for _, vi in x])
dp = [[2 * 10 ** 9 for j in range(v + 1)] for i in range(2)]
dp[0][0] = 0
dp[1][0] = 0

for i, (wi, vi) in enumerate(x):
    dp_pre = dp[1 - i % 2]
    dp_cur = dp[i % 2]
    for j in range(1, vi):
        dp_cur[j] = dp_pre[j]
    for j in range(vi, v + 1):
        dp_cur[j] = min(dp_pre[j], dp_pre[j - vi] + wi)
ans = 0
for vi, wi in enumerate(dp_cur):
    if wi <= w:
        ans = max(ans, vi)
print(ans)

Solution (Python):
import numpy as np
N,W = map(int,input().split())

dp = np.full(N*10**3+1, W+1, dtype = np.int64)
dp[0] = 0

for i in range(N):
    w,v = map(int,input().split())
    np.minimum(dp[:-v]+w, dp[v:], out = dp[v:])

for i in range(N*10**3+1):
    if dp[i] <= W:
        ans = i
print(ans)

Solution (Python):
N,W = map(int,input().split())
w,v = [0]*N,[0]*N
for i in range(N):
    w[i],v[i] = map(int,input().split())
V = sum(v)
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):
        if j-v[i] >= 0:
            dp[i+1][j] = dp[i][j-v[i]]+w[i]
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])

for i,d in enumerate(dp[N]):
    if d <= W:
        ans = i

print(ans)

Solution (Python):
N, W = map(int,input().split())
ws = []
vs = []
for _ in range(N):
   w,v = map(int,input().split())
   ws.append(w)
   vs.append(v)

def solve(N, W, ws, vs):
    
    V = sum(vs)

    
    dp = [W+1] * (V + 1)
    dp[0] = 0
    for i in range(N):
        
        v = vs[i]; w = ws[i]
        for j in range(V, v-1, -1):
            dp[j] = min(dp[j-v] + w, dp[j])

    
    return max(i for i in range(V+1) if dp[i] <= W)

print(solve(N,W,ws,vs))

Solution (Python):
N, W = map(int, input().split())
weight = []
value = []
for _ in range(N):
    w, v = map(int, input().split())
    weight.append(w)
    value.append(v)

dp = [[10**12]*(sum(value)+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for j in range(sum(value)+1 - value[i]):
        
        
        dp[i+1][j] = min(dp[i][j], dp[i+1][j])

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


ans = 0
for i in range(sum(value)+1):
    if dp[N][i] <= W:
        ans = i
print(ans)

Solution (Python):

n,w=map(int,input().split())
v=10**5
WV=[list(map(int,input().split())) for i in range(n)]

dp=[[10**10]*(v+1) for i in range(n+1)]
for i in range(n):
    dp[i][0]=0
for i in range(n):
    for j in range(v+1):
        if j-WV[i][1]>=0 and j-WV[i][1]<=v:
            dp[i+1][j]=min(dp[i][j-WV[i][1]]+WV[i][0], dp[i][j])
        else:
            dp[i+1][j]=dp[i][j]
for j in range(v, -1, -1):
    if dp[n][j]<=w:
        print(j)
        break

Solution (Python):
N,W=map(int,input().split())
w=[]
v=[]

for i in range(N):
    x,y=map(int,input().split())
    w.append(x)
    v.append(y)

S=sum(v)

DP=[1000000000000]*(S+1)
DP[0]=0


for i in range(N):
    for v1 in range(S,v[i]-1,-1):
        DP[v1]=min(DP[v1-v[i]]+w[i],DP[v1])

for i in range(S,0,-1):
    if DP[i]<=W:
        print(i)
        exit()

Solution (Python):
N,W=map(int,input().split())
w=[]
v=[]

for i in range(N):
    x,y=map(int,input().split())
    w.append(x)
    v.append(y)

S=sum(v)

DP=[[1000000000000]*(S+1) for i in range(N+1)]
for i in range(N+1):
    DP[i][0]=0



for i in range(N):
    for v1 in range(S+1):
        DP[i+1][v1]=min(DP[i][v1-v[i]]+w[i],DP[i][v1])

for i in range(S,0,-1):
    if DP[N][i]<=W:
        print(i)
        exit()

Solution (Python):
[n,w] = [int(i) for i in input().split()]
w_v = []
for i in range(n):
    w_v.append([int(j) for j in input().split()])

"""
dp[i][v] = w
i : 何番目までのものを使うか
v : ちょうどその価値になる
w : その時の重さ
最後に後ろから全探索して重さ超えてないやつ探す？
"""
INF = 10 ** 9 + 7
v_max = 10**3 * n + 1
dp = [[INF] * (v_max) for i in range(n)]


for i in range(n):
    dp[i][0] = 0
if n != 1:
    for i in range(n):
        
        if i != 0:
            for v_zantei in range(v_max):
                if v_zantei >= w_v[i][1]:
                    dp[i][v_zantei] = min(dp[i-1][v_zantei],dp[i-1][v_zantei - w_v[i][1]] + w_v[i][0])
                else:
                    dp[i][v_zantei] = dp[i-1][v_zantei]
            
        else:
            dp[i][w_v[i][1]] = w_v[i][0]
            
    ans = -1
    for v in range(v_max-1,-1,-1):
        
        if dp[n-1][v] <= w and ans < v:
            
            ans = v
    print(ans)
else:
    print(w_v[0][1])

Solution (Python):
def knapsack(N,W,weight,value):
    inf=float("inf")
    V=sum(value)
    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-value[i]>=0: 
                dp[i+1][j]=min(dp[i][j-value[i]]+weight[i], dp[i+1][j])
            
            dp[i+1][j]=min(dp[i][j],dp[i+1][j])

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

n,w=map(int,input().split())
weight=[0]*n
value=[0]*n
for i in range(n):
    weight[i],value[i]=map(int,input().split())
print(knapsack(n,w,weight,value))

Solution (Python):
n,W=map(int,input().split())
wv=[[int(i) for i in input().split()]for _ in range(n)]
dp=[W+1]*(10**5+1)
dp[0]=0
for i in range(0,n):
    w,v = wv[i]
    for j in range(10**5,v-1,-1):
        dp[j]=min(dp[j],dp[j-v]+w)
for i in range(10**5,-1,-1):
    if dp[i]<=W:
        print(i)
        break

Solution (Python):

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n,W = map(int,input().split())
weight = []
val = []
for i in range(n):
    a,b = map(int,input().split())
    weight.append(a)
    val.append(b)
max_v = sum(val) + 10 


INF = 10**12+7 
dp = [[INF]*(max_v+1) for i in range(n+1)]





for i in range(n+1):
    dp[i][0] = 0
for i in range(n):
    for j in range(max_v+1):
        if j-val[i] >= 0:
            
            dp[i+1][j] = min(dp[i][j],dp[i][j-val[i]]+ weight[i])
        else: dp[i+1][j] = dp[i][j]
    if i == n-1:
        
        
        
        for j in range(max_v,-1,-1):
            
            if dp[i+1][j] <= W:
                print(j)
                break

Solution (Python):

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n,W = map(int,input().split())
weight = []
val = []
for i in range(n):
    a,b = map(int,input().split())
    weight.append(a)
    val.append(b)
max_v = sum(val) + 10 


INF = 10**12+7 
dp = [[INF]*(max_v+1) for i in range(n+1)]





for i in range(n+1):
    dp[i][0] = 0
for i in range(n):
    for j in range(max_v+1):
        if j-val[i] >= 0:
            
            dp[i+1][j] = min(dp[i][j],dp[i][j-val[i]]+ weight[i])
        else: dp[i+1][j] = dp[i][j]
    if i == n-1:
        
        
        
        for j in range(1,max_v+1):
            
            if dp[i+1][-j] <= W:
                print(max_v - j + 1)
                break

Solution (Python):
n, ww = map(int, input().split())
w, v = [0] * n, [0] * n
for i in range(n):
    w[i], v[i] = map(int, input().split())

x = float("inf")

dp = [[x] * (100100) for i in range(110)]

dp[0][0] = 0
for i in range(n):
    for j in range(100100):
        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 i in range(100100):
    if dp[n][i] <= ww:
        ans = i

print(ans)

Solution (Python):
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
V = sum([v for _, v in wv])

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

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

Solution (Python):
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


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


def MI(): return map(int, input().split())


def S(): return input()


def MS(): return map(str, input().split())


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


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


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


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


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = {False: 'No', True: 'Yes'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']


show_flg = True
show_flg = False


def main():
    N, W = MI()
    V = 10 ** 3 * N
    dp = [IINF] * (V + 1)
    w = [0] * N
    v = [0] * N
    dp[0] = 0

    for i in range(N):
        w[i], v[i] = MI()

    for i in range(N):
        dp_next = [IINF] * (V + 1)
        for j in range(V+1):
            dp_next[j] = min(dp_next[j], dp[j])
            if j + v[i] <= V:
                dp_next[j+v[i]] = min(dp[j] + w[i], dp_next[j+v[i]])
        
        
        dp = dp_next

    ans = 0
    for i in range(V+1):
        if dp[i] != IINF and dp[i] <= W:
            ans = i

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
N,W = map(int,input().split())
wv = [list(map(int,input().split())) for i in range(N)]
DP = [[10**18 for i in range(10**5+1)] for j 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,10**5+1):
    DP[i][j] = min(DP[i][j],DP[i-1][j])
    if j-wv[i-1][1] >= 0:
      DP[i][j] = min(DP[i][j],DP[i-1][j-wv[i-1][1]]+wv[i-1][0])
for i in range(10**5+1):
  if DP[N][i] <= W:
    ans = i
print(ans)

Solution (Python):

N, W = map(int, input().split())
weight = []
value = []
for _ in range(N):
    w, v = map(int, input().split())
    weight.append(w)
    value.append(v)
dp = [[10**12] * (sum(value)+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for j in range(sum(value)+1 - value[i]):
        
        dp[i+1][j] = min(dp[i][j], dp[i+1][j])  
        
        dp[i+1][j+value[i]] = min(dp[i][j] + weight[i], dp[i+1][j+value[i]])  

ans = 0
for j in range(sum(value)+1):
    if dp[N][j] > W:
        continue
    ans = max(ans, j)
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7

def ii(): return int(sys.stdin.readline().rstrip()) 
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii())
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]

def ss(): return sys.stdin.readline().rstrip() 
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

n,w = mii()
wei=[]
val=[]
for i in range(n):
    ww,vv=map(int,input().split())
    wei.append(ww)
    val.append(vv)

dp=[[10**10]*(sum(val)+1) for i in range(n+1)]
dp[0][0]=0
for i in range(n):
    for j in range(sum(val)+1):
        if j>=val[i]:
            dp[i+1][j]=min(dp[i][j-val[i]]+wei[i],dp[i][j])
        else:
            dp[i+1][j]=dp[i][j]
ans=[]
for i in range(sum(val)+1):
    if dp[n][i]<=w:
        ans.append(i)
print(max(ans))

Solution (Python):
N, W = map(int, input().split())

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

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):
        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 i in range(V+1):
    if dp[N][i] <= W:
        ans = i
print(ans)

Solution (Python):
N, W = map(int, input().split())
w, v = [0] * N, [0] * N
for i in range(N):
	w[i], v[i] = map(int, input().split())

V = sum(v)
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):
		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)

Solution (Python):
N,W = map(int,input().split())
K = 10**5
dp = [[10**100 for i in range(K+1)] for j in range(N+1)]
dp[0][0] = 0
for i in range(1,N+1):
    w,v = map(int,input().split())
    for j in range(K+1):
        dp[i][j] = dp[i-1][j]
        if j < v:
            continue
        else:
            dp[i][j] = min(dp[i-1][j-v] + w,dp[i-1][j])
for i in range(K+1):
    x = dp[N][-i-1]
    if x <= W:
        print(K-i)
        quit()

Solution (Python):
N,W=map(int,input().split())
w=[0]*N
v=[0]*N

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

M=sum(v)

dp=[[10**9]*(M+1) for _ in range(N+1)]

for i in range(N+1):
    dp[i][0]=0
    
ans=0
for i in range(1,N+1):
    for j in range(1,M+1):
        dp[i][j]=dp[i-1][j]
        if j-v[i-1]>=0:
            new=dp[i-1][j-v[i-1]]+w[i-1]
            if new<=W:
                dp[i][j]=min(dp[i][j] , new)
                ans=max(ans,j)

print(ans)

Solution (Python):
import numpy as np
N, W = map(int, input().split())
WV = np.array([list(map(int, input().split())) for _ in range(N)])
max_V = WV[:, 1].max()

dp = np.full(N * max_V + 1, 10**10, dtype=np.int64)
dp[0] = 0
for w, v in WV:
    np.minimum(dp[v:], dp[:-v] + w, out=dp[v:])

dp[dp > W] = 0
ans = np.nonzero(dp)[0][-1]

print(ans)

Solution (Python):
n, w = map(int, input().split())
data = []
v_sum = 0
inf = 10**12
for i in range(n):
    data.append(list(map(int, input().split())))
    v_sum += data[i][1]

dp = [[inf for i in range(v_sum+1)] for j in range(n+1)]
dp[0][0] = 0
for i in range(1,n+1):
    weight, v = data[i-1]
    for j in range(v_sum+1):
        if j - v >= 0:
            dp[i][j] = min(dp[i-1][j], dp[i-1][j-v] + weight)
        else:
            dp[i][j] = dp[i-1][j]
ans = 0
for i in range(v_sum+1):
    if dp[-1][i] <= w:
        ans = max(ans, i)
print(ans)

Solution (Python):
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
def gcd(a,b):return fractions.gcd(a,b) 
def lcm(a,b):return (a*b) // fractions.gcd(a,b) 
def iin(): return int(input()) 
def ifn(): return float(input()) 
def isn(): return input().split() 
def imn(): return map(int, input().split()) 
def fmn(): return map(float, input().split()) 
def iln(): return list(map(int, input().split())) 
def iln_s(): return sorted(iln()) 
def iln_r(): return sorted(iln(), reverse=True) 
def fln(): return list(map(float, input().split())) 
def join(l, s=''): return s.join(l) 
def perm(l, n): return itertools.permutations(l, n) 
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) 
def comb(l, n): return itertools.combinations(l, n) 
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) 
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 
def add_mod(a,b): return (a+b) % MOD

N,W = imn()
wv = [iln() for _ in range(N)]
max_v = 10**3*100+1
dp =[[10**10 for _ in range(max_v)] for _ in range(N+1)]
dp[0][0] = 0

for i in range(N):
    for sum_v in range(max_v):
        if sum_v - wv[i][1] >= 0: 
            dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v-wv[i][1]]+wv[i][0])
        dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v])
ans = 0
for i in range(max_v):
    if dp[N][i] <= W: ans = i
print(ans)

Solution (Python):

"""
Created on Tue Jan 21 18:19:39 2020

@author: matsui
"""


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



M=int(sum(vi))
dp=[W+1]*(M+1)
dp[0]=0
   

s=0

for w, v in zip(wi,vi):
    s+=v
    for j in range(min(s,M),v-1,-1):
        if dp[j] > dp[j-v]+w: dp[j]=dp[j-v]+w
    

m=0
for i in range(M+1):
    if dp[i]<=W:
        m=i
print(m)

Solution (Python):
N,W = map(int,input().split())
WV = []
for i in range(N):
    WV.append(list(map(int,input().split())))
dp = [[float('inf') for j in range(100001)] for i in range(N)]
dp[0][0] = 0
for i in range(N):
    w,v = WV[i]
    if i == 0:
        dp[i][v] = w
    else:
        for j in range(100001):
            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]

ans = 0
for i,e in enumerate(dp[-1]):
    if W >= e:
        ans = i
print(ans)

Solution (Python):
n,w=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
dp=[[float('inf')]*(10**5+1) for i in range(n+1)]
dp[0][0]=0
for i in range(1,n+1):
  for j in range(10**5+1):
    if j-l[i-1][1]>=0:
      dp[i][j]=min(dp[i-1][j-l[i-1][1]]+l[i-1][0],dp[i][j])
    dp[i][j]=min(dp[i][j],dp[i-1][j])
for i in range(10**5+1):
  if w>=dp[n][10**5-i]:
    print(10**5-i)
    exit()

Solution (Python):
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
def gcd(a,b):return fractions.gcd(a,b) 
def lcm(a,b):return (a*b) // fractions.gcd(a,b) 
def iin(): return int(input()) 
def ifn(): return float(input()) 
def isn(): return input().split() 
def imn(): return map(int, input().split()) 
def fmn(): return map(float, input().split()) 
def iln(): return list(map(int, input().split())) 
def iln_s(): return sorted(iln()) 
def iln_r(): return sorted(iln(), reverse=True) 
def fln(): return list(map(float, input().split())) 
def join(l, s=''): return s.join(l) 
def perm(l, n): return itertools.permutations(l, n) 
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) 
def comb(l, n): return itertools.combinations(l, n) 
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) 
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 
MOD = 10**9+7

N,W = imn()
wv = [iln() for _ in range(N)]
max_v = 10**3*100+1

dp = [[10**10 for _ in range(max_v)] for _ in range(N+1)]
dp[0][0] = 0

for i in range(N):
    for sum_v in range(max_v):
        if wv[i][1] <= sum_v: 
            dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v-wv[i][1]]+wv[i][0])
        dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v])
ans = 0
for v in range(max_v):
    if dp[N][v] <= W: ans = v
print(ans)

Solution (Python):
N, W = map(int, input().split())
items = sorted([list(map(int, input().split())) for i in range(N)])
V = 10**5

dp = [[float("inf")]*(N + 1) for i in range(V + 1)]
dp[0] = [0]*(N + 1)
for i in range(V + 1):
    for j in range(N):
        k = i - items[j][1]
        dp[i][j + 1] = min(dp[i][j + 1], dp[i][j])
        if k < 0:
            break
        else:
            dp[i][j + 1] = min(dp[i][j + 1], dp[k][j] + items[j][0])

for i in range(V, -1, -1):
    for j in range(N + 1):
        if dp[i][j] <= W:
            print(i)
            exit()

Solution (Python):


N, W = list(map(int, input().split()))
item_list = []

for _ in range(N):
    w, v = list(map(int, input().split()))
    item_list.append((w, v))

max_v = (10 ** 3) * 100
dp_table = [[0] + [float("inf")] * (max_v + 1) for _ in range(N + 1)]
total_v = 0

for i in range(1, N + 1):  
    w, v = item_list[i - 1]
    
    total_v += v
    for j in range(total_v + 1):  
        
        dp_table[i][j] = dp_table[i - 1][j]
        before_min_weight = dp_table[i - 1][j]
        
        
        if j - v < 0:
            continue
        weight = dp_table[i - 1][j - v] + w
        min_weight = min(before_min_weight, weight)
        dp_table[i][j] = min_weight
        if i == N:
            if min_weight <= W:
                max_value = j

ans = max_value
print(ans)

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


if __name__ == '__main__':
    solve()