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):
def main():
    N, W =map(int, input().split())

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

    sum_v = sum(values)

    INF = 10**9+7

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


    for i in range(N):
        wi = weights[i]
        vi = values[i]
        for j in range(sum_v+1):
            if j < vi:
                dp[i+1][j] = dp[i][j]
            else:
                dp[i+1][j] = min(dp[i][j], dp[i][j-vi]+ wi)

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

    print(ans)

if __name__ == "__main__":
    main()

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

for i in range(n):
    ww, vv = map(int, input().split())
    w.append(ww)
    v.append(vv)

dp = [[float("inf")] * (n*(10**3+1)) for i in range(n + 1)]
dp[0][0] = 0

for i in range(n):
    for j in range(n*1001):
        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 i in range(n * 1001):
    if dp[n][i] <= mw:
        ans = i

print(ans)

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

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

    return ans

print(DP_E())

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

Solution (Python):
N, W = map(int, input().split())
A = list()
for n in range(N):
	A.append(list(map(int, input().split())))
inf = 10**10
V = 0
for a in range(N):
	V += A[a][1]
dp = [inf for v in range(V+1)]
dp[0] = 0
for p in range(N):
	for q in range(V - A[p][1], -1, -1):
		dp[q + A[p][1]] = min(dp[q + A[p][1]], dp[q] + A[p][0])

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

Solution (Python):
from collections import Counter
from collections import defaultdict
import math
import random
import heapq as hq
from math import sqrt
import sys
from functools import reduce


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


def iinput():
    return int(input())


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


def rinput():
    return map(int, tinput())


def rlinput():
    return list(rinput())


mod = int(1e9)+7


def factors(n):
    return set(reduce(list.__add__,
                      ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))




if __name__ == "__main__":
    n, weigh = rinput()
    w, v = [], []
    for i in range(n):
        wi, vi = rinput()
        w.append(wi)
        v.append(vi)

    mxv = sum(v)
    dp = [[99999999999 for i in range(mxv+1)]for j in range(n+1)]
    for i in range(n+1):
        dp[i][0]=0
    
    for item in range(1, n+1):
        for val in range(1, mxv+1):
            if v[item-1] <= val:
                dp[item][val] = min(
                    dp[item-1][val-v[item-1]]+w[item-1], dp[item-1][val])
            else:
                dp[item][val] = dp[item-1][val]
    
    ans=0
    for i in range(mxv+1):
        if dp[n][i]<=weigh:
            ans=i
    print(ans)

Solution (Python):
import sys

N, W = map(int, input().split())
WV = [list(map(int, sys.stdin.readline().split())) for i in range(N)]

INF = 10**10 + 1
dp = [[INF]*(N+1) for i in range(1000*N+2)]

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

i = 1


for j in range(1, N+1):
        for i in range(1, 1000*N+2):

        
                if i-WV[j-1][1]>=0:
                        dp[i][j] = min(dp[i-WV[j-1][1]][j-1]+WV[j-1][0], dp[i][j-1])
                else:
                        dp[i][j] = min(dp[i][j-1], WV[j-1][0])
        
        
                
        

for i in range(1000*N+2):
        if dp[i][N] > W:
                print(i-1)
                exit()

Solution (Python):
import sys

N, W = map(int, input().split())
WV = [list(map(int, sys.stdin.readline().split())) for i in range(N)]

INF = 10**10 + 1
dp = [[INF]*(N+1) for i in range(1000*N+2)]

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

i = 1


for i in range(1, 1000*N+2):
        for j in range(1, N+1):
                if i-WV[j-1][1]>=0:
                        dp[i][j] = min(dp[i-WV[j-1][1]][j-1]+WV[j-1][0], dp[i][j-1])
                else:
                        dp[i][j] = min(dp[i][j-1], WV[j-1][0])
        
        if dp[i-1][N] <= W and dp[i][N] > W:
                break
        

print(i-1)

Solution (Python):
import sys

N, W = map(int, input().split())
WV = [list(map(int, sys.stdin.readline().split())) for i in range(N)]

INF = 10**10 + 1
dp = [[INF]*(N+1) for i in range(1000*N+2)]

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

i = 1

while(True):
        for j in range(1, N+1):
                if i-WV[j-1][1]>=0:
                        dp[i][j] = min(dp[i-WV[j-1][1]][j-1]+WV[j-1][0], dp[i][j-1])
                else:
                        dp[i][j] = min(dp[i][j-1], WV[j-1][0])
        
        if dp[i-1][N] <= W and dp[i][N] > W:
                break
        i += 1

print(i-1)

Solution (Python):
import numpy as np
import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, W = map(int, input().split())
WV = [[int(x) for x in input().split()] for _ in range(N)]

INF = 10 ** 12
dp = [np.ones(10 ** 5 + 10, dtype=np.int64)*INF for _ in range(N + 1)]
dp[0][0] = 0

for i in range(N):
    w, v = WV[i]
    dp[i + 1][v:] = np.minimum(dp[i][v:], dp[i][:-v] + w)
    dp[i + 1][:v] = np.minimum(dp[i][:v], dp[i + 1][:v])

    

r = dp[N]
ans = np.where(r <= W)[0].max()

print(ans)

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

INF = 10 ** 12
L = 10 ** 5 + 1

dp = np.full(L, INF, dtype=int)
dp[0] = 0

for w, v in wvs:
    np.minimum(
        dp[:L-v] + w,
        dp[v:],
        out=dp[v:]
    )

answer, = np.where(dp <= W)
print(answer[-1])

Solution (Python):
import numpy as np
N,W=map(int,input().split())
dp=np.ones(10**5+1, dtype='int64')
dp[0]=0
dp[1:]=dp[1:]*(10**9+1)
for i in range(N):
    wi,vi=map(int,input().split())
    dp[vi:]=np.minimum(dp[vi:],dp[:-vi]+wi)
print(np.max(np.where(dp <= W)))

Solution (Python):
max_V = 100010
N,W = map(int, input().split())
lis = [[float('inf')] *(max_V) for _ in range(N+1)]
lis[0][0] = 0 
item = []
for i in range(N):
    w,v = map(int, input().split())
    item.append((w,v))
for i in range(1,N+1):
    for j in range(max_V):
        lis[i][j] = min(lis[i-1][j], (lis[i-1][j-item[i-1][1]] + item[i-1][0]))
ans = 0
for i in range(N+1):
    for j in range(max_V):
        if lis[i][j] <= W:
            ans = max(j, ans)
print(ans)

Solution (Python):
n, w = map(int, input().split())
weight = []
value = []

for i in range(n):
    x, y = map(int, input().split())
    weight.append(x)
    value.append(y)

dp = [[10 ** 9 + 7 for i in range(sum(value) + 1)] for j in range(n + 1)]

dp[0][0] = 0

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

        else:
            dp[i + 1][j] = dp[i][j]

a = sorted(range(sum(value) + 1), reverse = True)

for i in a:
    if dp[n][i] <= w:
        print(i)
        break

Solution (Python):
N, W = map(int, input().split())
K = [[0, 0] for _ in range(N)]
V = 0
for i in range(N):
    w, v = map(int, input().split())
    K[i] = [w, v]
    V += v
dp = [[float('inf')]*(V+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    w, v = K[i]
    for sum_v in range(V+1):
        if sum_v-v>=0:
            dp[i+1][sum_v] = min(dp[i][sum_v], dp[i][sum_v-v]+w)
        else:
            dp[i+1][sum_v] = dp[i][sum_v]
ans = 0
for i, d in enumerate(dp[-1]):
    if d<=W: ans = i
print(ans)

Solution (Python):








def resolve():
    N, W = map(int, input().split())
    weight, value = [0] * N, [0] * N
    for i in range(N):
        weight[i], value[i] = map(int, input().split())



    
    
    def knapsack(N, W, weight, value):

        V=sum(value)
        
        
        dp = [[float('inf')] * (V + 1) for _ in range(N + 1)]
        dp[0][0]=0

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

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

        return ans




    print(knapsack(N, W, weight, value))


resolve()

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())
w = [0] * N
v = [0] * N
for i in range(N):
    w[i], v[i] = map(int, input().split())
V = sum(v)
INF = float('inf')

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

Solution (Python):
N,W = list(map(int,input().split()))
DP = [[float('inf')]*(1000*N+1) for i in range(N+1)]
DP[0][0] = 0
V = 0
for i in range(1,N+1):
    w,v = list(map(int,input().split()))
    V += v
    for j in range(V+1):
        DP[i][j] = min(DP[i-1][j],DP[i-1][j-v]+w) if v <= j else DP[i-1][j]

for i in range(1000*N,-1,-1):
    if DP[N][i] <= W:
        print(i)
        break

Solution (Python):
n, w = 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(range(vi, MAX_V+1)):
        dp[sum_v] = min(dp[sum_v - vi] + wi, dp[sum_v])

ans = 0
for i in reversed(range(MAX_V+1)):
    if dp[i] <= w:
        print(i)
        exit()

Solution (Python):
n, w = 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(range(vi, MAX_V+1)):
        dp[sum_v] = min(dp[sum_v - vi] + wi, dp[sum_v])

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

Solution (Python):
import sys

input = sys.stdin.readline


def main():
    N, W = [int(x) for x in input().split()]
    WV = [[int(x) for x in input().split()] for _ in range(N)]

    sumv = 0
    for w, v in WV:
        sumv += v

    dp = [[10 ** 9 + 1] * (sumv + 1) for j in range(N + 1)]

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

    ans = 0
    for i in range(sumv + 1):
        if dp[N][i] > W:
            break
        else:
            ans = i

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys

input = sys.stdin.readline


def main():
    N, W = [int(x) for x in input().split()]
    WV = [[int(x) for x in input().split()] for _ in range(N)]

    sumv = 0
    for w, v in WV:
        sumv += v

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

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

    ans = 0
    for i in range(sumv + 1):
        if dp[N][i] > W:
            break
        else:
            ans = i

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
n,w  = map(int, (input().split()))
goods = [list(map(int, input().split())) for _ in range(n)]
MAX_V = sum(map(lambda x: x[1], goods))+1
INF = 10**19

dp = [[INF for _ in range(MAX_V)] for _ in range(n+1)]
dp[0][0] = 0

for i in range(1, n+1):
    for j in range(MAX_V):
        
        if j-goods[i-1][1] >= 0:
            dp[i][j] = min(dp[i-1][j-goods[i-1][1]]+goods[i-1][0], dp[i-1][j])
        else:
            dp[i][j] = dp[i-1][j]

ans = 0
for i in range(MAX_V):
    if dp[n][i] <= w:
        ans = max(ans, i)

print(ans)

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

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

for i in range(1, N+1):
  for j in range(total_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])
for i in range(total_v, -1, -1):
  if dp[N][i] <= W:
    print(i)
    break

Solution (Python):
n, w = map(int, input().split())
nums = []
for _ in range(n):
  nums.append(list(map(int, input().split())))
  
total_v = sum(nums[i][1] for i in range(n))

dp = [[float('inf') for _ in range(total_v+1)] for _ in range(n+1)]
dp[0][0] = 0

for i in range(1, n+1):
  for j in range(total_v+1):
    if j < nums[i-1][1]:
      dp[i][j] = dp[i-1][j]
    else:
      dp[i][j] = min(dp[i-1][j], dp[i-1][j-nums[i-1][1]] + nums[i-1][0])
for i in range(total_v, -1, -1):
  if dp[n][i] != float('inf') and dp[n][i] <= w:
    print(i)
    break

Solution (Python):



import sys
input = sys.stdin.readline
import numpy as np

n, W = map(int, input().split())
dp = np.full(10**5 + 1, 10**12, dtype='int64')
dp[0] = 0 
for _ in range(n):
    w, v = map(int, input().split())
    dp[v:] = np.minimum(dp[:-v]+w, dp[v:])


print(np.where(dp <= W)[0][-1])

Solution (Python):
from bisect import bisect_left
def main():
    n, w = map(int, input().split())
    item = [list(map(int, input().split())) for _ in range(n)]
    dp = [w+1]*(10**5+1)
    dp[0] = 0
    item.sort(key=lambda x: x[1])
    x = 0
    for p, q in item:
        for i in reversed(range(q, min(len(dp), x+q+1))):
            dp[i] = min(dp[i-q]+p, dp[i])
        x += q
    ans = 0
    for i in reversed(range(len(dp))):
        if dp[i] <= w:
            ans = i
            break
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
import numpy as np 
N,W=map(int,input().split())
w,v=[],[]
for i in range(N):
    a,b=map(int,input().split())
    w+=[a]
    v+=[b]
DP=np.ones(N*1000+1,dtype=int)*(W+1)
DP[0]=0
for i in range(N):
    DP[v[i]:]=np.minimum(DP[:-v[i]]+w[i],DP[v[i]:])
ans=0
for k in range(N*1000+1):
    if DP[k]<=W:
        ans=k
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())
    
dp = [[10**9+1]*(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):
        if j >= v[i]:
            dp[i+1][j] = min(dp[i][j-v[i]]+w[i],dp[i][j])
        else:
            dp[i+1][j] = dp[i][j]
            
ans = 0

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

Solution (Python):
N, W = map(int, input().split())
w = []
v = []
sum_value = 0
inf = 10**9 + 1
for _ in range(N):
    w_, v_ = map(int, input().split())
    w.append(w_)
    v.append(v_)
    sum_value += v_

"""
dp[n][i]: n個目までの品物から価値の総量がiよりも大きくなるように選択したときの, 重さの最小値
"""

dp = [[inf] * (sum_value+1) for _ in range(N+1)]
dp[0][0] = 0


for n in range(1, N+1):
    for i in range(sum_value+1):
        if i >= v[n-1]:
            dp[n][i] = min(dp[n-1][i], dp[n-1][i-v[n-1]] + w[n-1])
        else:
            dp[n][i] = dp[n-1][i]
for i in range(sum_value+1)[::-1]:
    if dp[N][i] != inf and dp[N][i] <= W:
        print(i)
        break

Solution (Python):
N, W = map(int, input().split())
V = 10 ** 5
inf = 10 ** 18
dp = [inf] * (V + 1)
dp[0] = 0

for n in range(1, N+1):
    w, v = map(int, input().split())
    for i in range(v, V+1)[::-1]:
        if dp[i-v]+w <= W:
            dp[i] = min(dp[i], dp[i-v]+w)

for i in range(V+1)[::-1]:
    if dp[i] < inf:
        print(i)
        break

Solution (Python):

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    
    from itertools import combinations, permutations
    
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    

    mod = 1000000007

    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 = 10**5+1
    inf = float('inf')
    dp = [inf]*V
    dp[0] = 0

    for i in range(N):
        for j in range(V-1, v[i]-1, -1):
            if dp[j-v[i]]+w[i]<=W:
                dp[j] = min(dp[j], dp[j-v[i]]+w[i])
    
    res = 0
    for i, x in enumerate(dp):
        if x <= W:
            res = i
    print(res)
    
if __name__ == '__main__':
    main()

Solution (Python):



def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    
    from itertools import combinations, permutations
    
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    

    

    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 = 10**5+1
    inf = float('inf')
    dp = [inf]*V
    dp[0] = 0
    for i in range(N):
        for j in range(V, v[i]-1, -1):
            if dp[j-v[i]]+w[i]<=W:
                dp[j] = min(dp[j], dp[j-v[i]]+w[i])
    for i in range(V):
        if dp[-(i+1)]<=W:
            print(V-(i+1))
            exit()
            
if __name__ == '__main__':
    main()

Solution (Python):
N, W = map(int, input().split())
A = list()
for n in range(N):
	A.append(list(map(int, input().split())))
inf = 10**10
V = 0
for a in range(N):
	V += A[a][1]
dp = [inf for v in range(V+1)]
dp[0] = 0
for p in range(N):
	for q in range(V - A[p][1], -1, -1):
		dp[q + A[p][1]] = min(dp[q + A[p][1]], dp[q] + A[p][0])

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

Solution (Python):
n, w = map(int, input().split())

inf = 10 ** 10
dp = [[inf] * (10**5+3) for _ in range(n+1)]
dp[0][0] = 0
for i in range(n):
    weight, value = map(int, input().split())
    for j in range(10**5 + 3):
        if j - value >= 0:
            dp[i+1][j] = min(
                dp[i][j - value] + weight,
                dp[i][j]
            )
        else:
            dp[i+1][j] = dp[i][j]
for i in reversed(range(10**5+3)):
    if dp[n][i] <= w:
        print(i)
        break

Solution (Python):
import numpy as np
n,w = map(int,input().split())
dp = np.full(100001,w+1,dtype=int)
dp[0] = 0
for i in range(n):
    we,va = map(int, input().split())
    dp[va:] = np.minimum(dp[va:],dp[:-va]+we)
print(np.max(np.where(dp <= w)))

Solution (Python):
import sys

N, W = map(int, input().split())
WV = [list(map(int, sys.stdin.readline().split())) for i in range(N)]
'''
w = [0]*N
v = [0]*N
for i in range(N):
        w[i], v[i] = map(int, sys.stdin.readline().split())
'''
INF = 10**11+1
dp = [[INF]*(N+1) for j in range(N*(10**3)+10)]
i = 0
ans = INF
while(True):
        for j in range(1, N+1):
                
                w = WV[j-1][1]
                if i-w >= 0:
                        dp[i][j] = min(dp[i][j-1], dp[i-w][j-1]+WV[j-1][0])
                        
                else:
                        dp[i][j] = min(dp[i][j-1], WV[j-1][0])
        
        
        if dp[i][N] > W and ans <= W:
                print(i)
                exit()
        ans = dp[i][N]
        '''
        if dp[i][N] >= W:
                if ans == 0:
                        ans = dp[i][N]
                elif ans < dp[i][N]:
                        print(i)
                        exit()
                print(i, ans)
        '''
        i += 1

Solution (Python):
import sys

N, W = map(int, input().split())
WV = [list(map(int, sys.stdin.readline().split())) for i in range(N)]
'''
w = [0]*N
v = [0]*N
for i in range(N):
        w[i], v[i] = map(int, sys.stdin.readline().split())
'''
INF = 10**11+1
dp = [[INF]*(N+1) for j in range(N*(10**3)+10)]
i = 1
ans = INF
while(True):
        for j in range(1, N+1):
                
                w = WV[j-1][1]
                if i-w > 0:
                        dp[i][j] = min(dp[i][j-1], dp[i-w][j-1]+WV[j-1][0])
                        
                else:
                        dp[i][j] = min(dp[i][j-1], WV[j-1][0])
        
        
        if dp[i][N] > W and ans <= W:
                print(i-1)
                exit()
        ans = dp[i][N]
        '''
        if dp[i][N] >= W:
                if ans == 0:
                        ans = dp[i][N]
                elif ans < dp[i][N]:
                        print(i)
                        exit()
                print(i, ans)
        '''
        i += 1

Solution (Python):
N, W = map(int, input().split())
item = [[0] * 2 for _ in range(N)]
for i in range(N):
    w, v = map(int, input().split())
    item[i][0], item[i][1] = w, v
dp = [[1000000001] * (1000*N+1) for i in range(N+1)]
dp[0][0] = 0
for i in range(1, N+1):
    for j in range(1000*N+1):
        if item[i-1][1] <= j:
            dp[i][j] = min(dp[i-1][j-item[i-1][1]] + item[i-1][0], dp[i-1][j])
        else:
            dp[i][j] = dp[i-1][j]
ans = 0
for i in range(1000*N+1):
    if dp[N][i] <= W:
        ans = i
print(ans)

Solution (Python):
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))



sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, W = MAP()
L = [LIST() for _ in range(N)]

V = 0

for w, v in L:
    V += v

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


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


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

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)]
f_max = 10**9+100 

dp = [[f_max] * (10**5 +100) for _ in range(N+1)]
def chmin(a, b):
    if a > b:
        return b
    else:
        return a
def chmax(a,b):
    if a < b:
        return b
    else:
        return a
def main():
    
    dp[0][0]=0
    for i in range(1,N+1):
        w,v = wv[i-1][0], wv[i-1][1]
        for sum_v in range(10**5+1):
            if sum_v - v >= 0:
                dp[i][sum_v] = chmin(dp[i][sum_v], dp[i-1][sum_v-v]+ w)
            
            dp[i][sum_v] = chmin(dp[i][sum_v],dp[i-1][sum_v])
    
    ans = 0
    for i in range(10**5+100):
        if dp[N][i] <= W:
            ans = i
    
    print(ans)  

            
 

if __name__ == "__main__":
    main()

Solution (Python):


import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni = lambda: int(ns())
nin = lambda y: [ni() for _ in range(y)]
na = lambda: list(map(int, stdin.readline().split()))
nan = lambda y: [na() for _ in range(y)]
nf = lambda: float(ns())
nfn = lambda y: [nf() for _ in range(y)]
nfa = lambda: list(map(float, stdin.readline().split()))
nfan = lambda y: [nfa() for _ in range(y)]
ns = lambda: stdin.readline().rstrip()
nsn = lambda y: [ns() for _ in range(y)]
ncl = lambda y: [list(ns()) for _ in range(y)]
nas = lambda: stdin.readline().split()

N, W = na()
wv = nan(N)
MAX_V = 100100
dp = [[inf] * MAX_V for _ in range(N + 1)]
dp[0][0] = 0

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

ans = inf
for i in range(MAX_V):
    if dp[N][i] <= W:
        ans = i

print(ans)

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())
sv = sum(v)
dp = [[int(1e10)] * (sv+1) for i in range(N + 1)]
dp[0][0] = 0
for i in range(1, N + 1):
    for j in range(sv + 1):
        if j - v[i-1] >= 0:
            dp[i][j] = min(dp[i-1][j], dp[i-1][j - v[i-1]] + w[i-1])
        else:
            dp[i][j] = dp[i-1][j]

ans = sv
while(dp[N][ans] > W):
    ans -= 1
print(ans)

Solution (Python):
N, W = map(int, input().split())
l = []
for i in range(N):
  L = list(map(int, input().split()))
  l.append(L)
sum_of_weight = 0
sum_of_value = 0
for i in range(N):
  sum_of_weight += l[i][0]
  sum_of_value += l[i][1]
dp = [[sum_of_weight+1 for i in range(sum_of_value+1)] for j in range(N+1)]
dp[0][0] = 0
for i in range(1,N+1):
  for j in range(sum_of_value+1):
    if j >= l[i-1][1]:
      dp[i][j] = min(dp[i-1][j], dp[i-1][j-l[i-1][1]]+l[i-1][0])
    else:
      dp[i][j] = dp[i-1][j]
ans = 0
for i in range(N+1):
  for j in range(sum_of_value+1):
    if W >= dp[i][j] and ans < j:
      ans = j
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]:
            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
for j in range(V+1):
    if dp[N][j] <= W:
        ans = j
print(ans)

Solution (Python):
n, w = 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 range(MAX_V, vi-1, -1):
        dp[sum_v] = min(dp[sum_v - vi] + wi, dp[sum_v])

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

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())

inf=float("inf")
sumV=sum(v)
dp=[[inf]*(sumV+1) for i in range(N+1)]
dp[0][0]=0

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

ans=0
for g in range(len(dp[-1])):
    if dp[-1][g]<=W:
        ans=g

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
import numpy as np
N,W=map(int,input().split())
max_Vi = 10**3
max_Wi = W
dp=[0]+[max_Wi+1]*(N*max_Vi)
dp=np.array(dp)
for i in range(N):
  wi,vi=map(int,input().split())
  dp[vi:]=np.minimum(dp[vi:],dp[:-vi]+wi)
print(np.max(np.where(dp <= W)))

Solution (Python):
import sys
input = sys.stdin.readline
import numpy as np
N,W=map(int,input().split())
dp=np.ones(10**5+1, dtype='int64')
dp[0]=0
dp[1:]=dp[1:]*(10**9+1)
for i in range(N):
  wi,vi=map(int,input().split())
  dp[vi:]=np.minimum(dp[vi:],dp[:-vi]+wi)
print(np.max(np.where(dp <= W)))

Solution (Python):
import numpy as np
n, w = map(int, input().split())
wv = [tuple(map(int, input().split())) for _ in range(n)]

INF = 10**9 + 100
MAX_V = 10 ** 6

dp = np.full((n+1, MAX_V), INF, np.int64)
dp[0][0] = 0

for i, (wi, vi) in enumerate(wv):
    dp[i+1] = dp[i]
    np.minimum(dp[i][vi:], dp[i][:-vi] + wi, out=dp[i+1][vi:])

ans = np.where(dp[n] <= w)[0][-1]
print(ans)

Solution (Python):
dp = [[float('inf') for _ in range(10**5+10)] for _ in range(10**2+10)]

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

for i in range(N):
    wi,vi = map(int,input().split())

    w.append(wi)
    v.append(vi)


dp[0][0] = 0

for i in range(N):
    for sum_v in range(10**5+10):
        if v[i] <= sum_v:
            dp[i+1][sum_v] = min(dp[i][sum_v], dp[i][sum_v-v[i]] + w[i])
        else:
            dp[i+1][sum_v] = dp[i][sum_v]
            

res = 0

for i in range (10**5+10):
    if (dp[N][i] <= W):
        res = i

print(res)

Solution (Python):
import numpy as np  

n, w = map(int, input().split())
dp = np.full(n*1000+1, float('inf'))
dp[0] = 0

for _ in range(n):
    weight, value = map(int, input().split())
    dp[value:] = np.minimum(dp[value:], dp[:-value] + weight) 

print(np.max(np.where(dp <= w)))

Solution (Python):
'''

                            Online Python Compiler.
                Code, Compile, Run and Debug python program online.
Write your code in this editor and press "Run" button to execute it.

'''

firstline = str(input())
firstline = firstline.split()
n = int( firstline[0] )
total = int( firstline[1] )

maxvalue = int( pow(10, 5) + 1)

colums = [10000000001000000000 for _ in range(maxvalue)]
dp = [ colums[::] for _ in range(n+1) ]

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

stone = []

for i in range(n):
    getInput = str(input())
    getInput = getInput.split()
    stone.append(( int(getInput[1]) , int(getInput[0]) ) )

stone = sorted(stone)

index = 0
for currentstone in stone:
    currentvalue = currentstone[0]
    currentweight = currentstone[1]
    index += 1 
    for V in range(1, maxvalue):
        if currentvalue <= V:
            dp[index][V] = min(currentweight + dp[index-1][V - currentvalue], dp[index - 1][V])
        else:
            dp[index][V] = dp[index-1][V]

bestvalue = 0
for i in range(1, maxvalue ):
    if dp[n][i] <= total and dp[n][i] !=9999999 :
        bestvalue = i


print(bestvalue)