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^5

1 \leq w_i \leq W

1 \leq v_i \leq 10^9

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

5 5
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000

Sample Output 2

5000000000

The answer may not fit into a 32-bit integer type.

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.



Sample input:
3 8
3 30
4 50
5 60


Sample output:
90

Submission status: Runtime Error

Solution code:
import numpy as np

N, W = map(int, input().split())
wv = [[0,0]]
for _ in range(N):
    wv.append([ list(map(int, input().split())) ])
# N,W = 3, 8
# wv = [[0,0],[3,30], [4,50], [5,60]]
dp = np.array([ [0]*(W+1) ] * (N+1))
# print(dp.shape)
# print(np.array(dp))

for n in range(1,N+1):
    for w_lim in range(1,W+1):
        # print(n, w_lim)
        # print(np.array(dp))
        # v[n]を追加するとき
        if w_lim - wv[n][0] >= 0 :
            dp[n][w_lim] = max( dp[n-1][w_lim], dp[n-1][w_lim-wv[n][0]]+wv[n][1] )
        else :
            dp[n][w_lim] = dp[n-1][w_lim]

# print('\n',np.array(dp))
print(dp[N][W])

Submission status: Runtime Error

Solution code:
import sys
import math
from  collections import defaultdict

sys.setrecurisonlimit(1000000000)

# sys.stdin = open('input.txt', 'r')
# sys.stdout = open('output.txt', 'w')

def solve(test):
	n, w = map(int, input().split())
	val = [None] * n
	wgt = [None] * n
	for i in range(n):
		wgt[i], val[i] = map(int, input().split())
	dp = {}
	ans = knapsack(wgt, val, 0, n, dp, w)
	print(ans)

def knapsack(wgt, val, i, n, dp, w):
	if (i, w) in dp:
		return dp[(i, w)]
	elif i >= n:
		return 0
	else:
		dp[(i, w)] = knapsack(wgt, val, i + 1, n, dp, w)
		if wgt[i] <= w:
			dp[(i, w)] = max(dp[(i, w)], val[i] + knapsack(wgt, val, i + 1, n, dp, w - wgt[i]))
		return dp[(i, w)]


if __name__ == "__main__":
	test_cases = 1
	for t in range(1, test_cases + 1):
		solve(t)

Submission status: Runtime Error

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

dp = [[0]*(W+1) for j in range(N+1)]

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

print(dp[N][W])

Submission status: Runtime Error

Solution code:
class Solution:
	def __init__(self):
		pass
	def knapsack01(self,totalWeight,choices):
		dp=[[0]*totalWeight for _ in choices.keys()]
		keys=sorted(list(choices.keys()))
		for i in range(len(dp[0])):
			dp[0][i]=choices[keys[0]] if i+1>=keys[0] else 0
		for i in range(1,len(dp)):
			for j in range(len(dp[0])):
				if j+1>=keys[i]:
					#dp[i][j]=max(dp[i-1][j],max(choices[keys[i]]) + (dp[i-1][j-keys[i]] if j-keys[i]>=0 else 0))
					dp[i][j]=max(max(choices[keys[i]]) + (dp[i-1][j-keys[i]] if j-keys[i]>=0 else 0), dp[i-1][j])
				else:
					dp[i][j]=dp[i-1][j]
		return dp[-1][-1]
obj=Solution()
n,w=map(int,input().split())
choices={}
for _ in range(n):
	wi,v=map(int,input().split())
	try:
		choices[wi].append(v)
	except:
		choices[wi]=[v]
print(obj.knapsack01(w,choices))
#print(obj.knapsack01(8,{5:60,3:30,4:50}))

Submission status: Runtime Error

Solution code:
class Solution:
	def __init__(self):
		pass
	def knapsack01(self,totalWeight,choices):
		dp=[[0]*totalWeight for _ in choices.keys()]
		keys=sorted(list(choices.keys()))
		for i in range(len(dp[0])):
			dp[0][i]=choices[keys[0]] if i+1>=keys[0] else 0
		for i in range(1,len(dp)):
			for j in range(len(dp[0])):
				if j+1>=keys[i]:
					#dp[i][j]=max(dp[i-1][j],max(choices[keys[i]]) + (dp[i-1][j-keys[i]] if j-keys[i]>=0 else 0))
					dp[i][j]=max(max(choices[keys[i]]) + (dp[i-1][j-keys[i]] if j-keys[i]>=0 else 0), dp[i-1][j])
				else:
					dp[i][j]=dp[i-1][j]
		return dp[-1][-1]
obj=Solution()
n,w=map(int,input().split())
choices={}
for _ in range(n):
	wi,v=map(int,input().split())
	choices=choices.get(wi,[]).append(v)
print(obj.knapsack01(w,choices))
#print(obj.knapsack01(8,{5:60,3:30,4:50}))

Submission status: Runtime Error

Solution code:
class Solution:
	def __init__(self):
		pass
	def knapsack01(self,totalWeight,choices):
		dp=[[0]*totalWeight for _ in choices.keys()]
		keys=sorted(list(choices.keys()))
		for i in range(len(dp[0])):
			dp[0][i]=choices[keys[0]] if i+1>=keys[0] else 0
		for i in range(1,len(dp)):
			for j in range(len(dp[0])):
				if j+1>=keys[i]:
					dp[i][j]=max(choices[keys[i]],choices[keys[i]] + (dp[i-1][j-keys[i]] if j-keys[i]>=0 else 0))
				else:
					dp[i][j]=dp[i-1][j]
		return dp[-1][-1]
obj=Solution()
n,w=map(int,input().split())
choices={}
for _ in range(n):
	wi,v=map(int,input().split())
	choice[wi]=v
print(obj.knapsack01(w,choices))
#print(obj.knapsack01(8,{5:60,3:30,4:50}))

Submission status: Runtime Error

Solution code:
class Solution:
	def __init__(self):
		pass
	def knapsack01(self,totalWeight,choices):
		dp=[[0]*totalWeight for _ in choices.keys()]
		keys=sorted(list(choices.keys()))
		for i in range(len(dp[0])):
			dp[0][i]=choices[keys[0]] if i+1>=keys[0] else 0
		for i in range(1,len(dp)):
			for j in range(len(dp[0])):
				if j+1>=keys[i]:
					dp[i][j]=max(choices[keys[i]],choices[keys[i]] + (dp[i-1][j-keys[i]] if j-keys[i]>=0 else 0))
				else:
					dp[i][j]=dp[i-1][j]
		return dp[-1][-1]
obj=Solution()
n,w=map(int,input.split())
choices={}
for _ in range(n):
	wi,v=map(int,input.split())
	choice[wi]=v
print(obj.knapsack01(w,choices))
#print(obj.knapsack01(8,{5:60,3:30,4:50}))

Submission status: Runtime Error

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

DP = {0: 0}
for i in range(N):
    wi, vi = map(int, input().split())
    for j in DP:
        if j+wi <= W:
            DP_dst[j+wi] = max(DP.get(j+wi, 0), DP[j]+vi)
    DP = DP_dst
print(max((DP[x] for x in DP)))

Submission status: Runtime Error

Solution code:
def e():
    import numpy as np

    N, W = map(int, input().split())

    dp = np.zeros(W+1, dtype=np.int64)

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

    print(dp[-1])


##########
if __name__ == "__main__":
    e()

Submission status: Runtime Error

Solution code:
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())

dp=[[0]*(n+10) for i in range(100100)]
for i in range(n):
    for sum_w in range(w+1):
        # i番目の品物を選ぶ場合
        if sum_w -  weight[i] >= 0:
            dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w - weight[i]]+value[i])
        # i番目の品物を選ばない場合
        dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])
print(dp[n][w])

Submission status: Runtime Error

Solution code:
mport numpy as np
N, W = map(int, input().split())
dp = np.zeros(W+1, dtype=np.int64)
for _ in range(N):
    w,v = map(int, input().split())
    np.maximum(dp[w:], dp[:-w] + v , dp[w:])
print(max(dp))

Submission status: Runtime Error

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

dp = [[0 for _ in range(101)] for _ in range(10**5+10)]

for w in range(1, W+1):
    for n in range(N):
        Wi = wv[n][0]
        Vi = wv[n][1]
        if Wi <= w:
            dp[n+1][w] = max(dp[n][w], dp[n][w-Wi] + Vi)
        dp[n+1][w] = max(dp[n][w], dp[n+1][w])

print(dp[N][W])

Submission status: Runtime Error

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

dp = [[0 for _ in range(101)] for _ in range(10**5+10)]

for w in range(1, W+1):
    for n in range(N):
        Wi = wv[n][0]
        Vi = wv[n][1]
        if Vi <= w:
            dp[n+1][w] = max(dp[n][w], dp[n][w-Wi] + Vi)

print(dp[N][W+1])

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
def main():
    N, W = map(int, readline().split())
    weight = [0 for _ in range(110)]
    value = [0 for _ in range(110)] 
    for i in range(N):
        w, v = map(int, readline().split())
        weight[i] = w
        value[i] = v
    dp = [[0 for _ in range(110)] for _ in range(10**5+100)]
    for i in range(N):
        for sum_w in range(W+1):
            if sum_w - weight[i] >= 0:
                dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w-weight[i]] + value[i]) 
            dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])
    print(dp[N][W])
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
if __name__ == "__main__":
    print(main())

Submission status: Runtime Error

Solution code:
N, W =map(int, input().split())
weight = [0] * 110
value = [0] * 110
dp = [[0] * (110) for _ in range(10010)]

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

for i in range(N):
    for w in range(W + 1):# <= を表現したいときは+1するとよいかも
        if(w >= weight[i]):
            dp[i + 1][w] = max(dp[i][w - weight[i]] + value[i], dp[i][w])
        else:
            dp[i + 1][w] = dp[i][w]
#print(weight[:N],value[:N])
print(dp[N][W])

Submission status: Runtime Error

Solution code:
n,v=[int(k) for k in input().split()]
li=[]
for i in range(n):
  li.append([int(k) for k in input().split()])
  
dp=[[0 for i in range(v+1)] for j in range(n+1)]
for a in range(1,n+1):
  for b in range(1,v+1):
    if(li[a-1][0]<=b):
      dp[a][b]=max(li[a-1][1]+dp[a-1][b-li[a-1][0]],dp[a-1][b])
    else:
      dp[a][b]=dp[a-1][b]
print(dp[n][v]%mod)

Submission status: Runtime Error

Solution code:
n,v=[int(k) for k in input().split()]
li=[]
for i in range(n):
  li.append([int(k) for k in input().split()])
mod=10**9+7  
dp=[[0 for i in range(v+1)] for j in range(n+1)]
for a in range(1,n+1):
  for b in range(1,v+1):
    if(li[a-1][0]<=b):
      dp[a][b]=max((li[a-1][1]+dp[a-1][b-li[a-1][0]]),dp[a-1][b])
    else:
      dp[a][b]=dp[a-1][b]
print(dp[n][v])

Submission status: Runtime Error

Solution code:
v,n=[int(k) for k in input().split()]
li=[]
for i in range(n):
  li.append([int(k) for k in input().split()])
  
dp=[[0 for i in range(v+1)] for j in range(n+1)]
for a in range(1,n+1):
  for b in range(1,v+1):
    if(li[a-1][0]<=b):
      dp[a][b]=max(li[a-1][1]+dp[a-1][b-li[a-1][0]],dp[a-1][b])
    else:
      dp[a][b]=dp[a-1][b]
print(dp[n][v])

Submission status: Runtime Error

Solution code:
n, W = [int(x) for x in raw_input().split()]
ans = 0
dp = [0 for _ in range(W+1)]
for i in range(n):
    weight, value = [int(x) for x in raw_input().split()]    
    for w in reversed(range(W+1)):
        if w >= weight:
            dp[w] = max(dp[w], dp[w-weight]+value)

ans = max(dp)

print(ans)

Submission status: Runtime Error

Solution code:
N,W=map(int,input().split())
dp = [0]*(capacity + 1)

def solve_knapsack(capacity):
    # basic checks
 
    
    # populate the capacity = 0 columns, with '0' capacity we have '0' profit

    for i in range(0, N):
        weights,profits = map(int,input().split())
        for c in range(capacity, weights-1, -1):
            tmp = profits + dp[c - weights]
            if tmp > dp[c]: dp[c] = tmp
 
    # maximum profit will be at the bottom-right corner.
    return dp[capacity]
  
def main():
 
    res = solve_knapsack(W)
 
    print(res)
if __name__ == "__main__":
	main()

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline


N,W=map(int,input().split())

def solve_knapsack(capacity):
    # basic checks
    n = len(profits)
 
    dp = [0]*(capacity + 1)
    # populate the capacity = 0 columns, with '0' capacity we have '0' profit

    for i in range(0, n):
        weights,profits = map(int,input().split())
        for c in range(capacity, weights-1, -1):
            tmp = profits + dp[c - weights
            if tmp > dp[c]: dp[c] = tmp
 
    # maximum profit will be at the bottom-right corner.
    return dp[capacity]
  
def main():
 
    res = solve_knapsack(W)
 
    print(res)
if __name__ == "__main__":
	main()

Submission status: Runtime Error

Solution code:
def solve_knapsack(profits, weights, capacity):
  # create a two dimensional array for Memoization, each element is initialized to '-1'
	dp = [[-1 for x in range(capacity+1)] for y in range(len(profits))]
    return knapsack_recursive(dp, profits, weights, capacity, 0)


def knapsack_recursive(dp, profits, weights, capacity, currentIndex):

  # base checks
    if capacity <= 0 or currentIndex >= len(profits): return 0

  # if we have already solved a similar problem, return the result from memory
    if dp[currentIndex][capacity] != -1: return dp[currentIndex][capacity]

  # recursive call after choosing the element at the currentIndex
  # if the weight of the element at currentIndex exceeds the capacity, we
  # shouldn't process this
    profit1 = 0
    if weights[currentIndex] <= capacity:
        profit1 = profits[currentIndex] + knapsack_recursive(dp, profits, weights, capacity - weights[currentIndex], currentIndex + 1)

  # recursive call after excluding the element at the currentIndex
    profit2 = knapsack_recursive(dp, profits, weights, capacity, currentIndex + 1)

    dp[currentIndex][capacity] = max(profit1, profit2)
    return dp[currentIndex][capacity]
  
def main():
    N,W=map(int,input().split())
    w,v=map(int,input().split())
    res = solve_knapsack(v, w, W)

    print(res)
if __name__ == "__main__":
	main()

Submission status: Runtime Error

Solution code:
def ks(val, w, W, n):


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

    for i in range(1, n + 1):
        for j in range(1, W + 1):

            if j - w[i - 1] >= 0:
                dp[i][j] = max(val[i - 1] + dp[i - 1][j - w[i - 1]], dp[i - 1][j])

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

    return dp[n][W]


# n, k = get_ints()
# arr = get_array()

# sys.stdout.write(str(frog_1(arr, n, k)))

n, W = list(map(int, sys.stdin.readline().split()))
val = []
weights = []
for i in range(n):
    w, v = list(map(int, sys.stdin.readline().strip().split()))
    val.append(v)
    weights.append(w)

sys.stdout.write(str(ks(val, weights, W, n)))

Submission status: Runtime Error

Solution code:

N,W = map(int,input().split())
w,v = [0 for _ in range(N)],[0 for _ in range(N)]

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

dp = [[0 for _ in range(110)] for _ in range(100100)]

for i in range(N):
    for sum_w in range(0,W+1):
        if sum_w - w[i] >= 0:
            dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w - w[i]] + v[i])

        dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])

#dp[i]][sum_w]
print(dp[N][W])

Submission status: Runtime Error

Solution code:
import numpy as np
n,W=map(int,input().split()
wv=[list(map(int,input().split())) for i in range(n)]
wv=np.array(wv)
dp=[0]*(W+1)
dp=np.array(dp)
for w,v in wv:
  dp[w:]=np.maximum(dp[w:],dp[:-w]+v)
print(dp[W])

Submission status: Runtime Error

Solution code:
impport numpy as np
n,w=map(int,input())
wv=list(map(int,input().split()))
wv=np.array(wv)
dp=[0]*(w+1)
dp=np.array(dp)
for w,v in wv:
  dp[w:]=max(dp[w:],dp[:-w]+v)
print(dp[w])

Submission status: Runtime Error

Solution code:
N, W = map(int, input().split())
W = []
V = []

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

Ans = [[0 for _ in range(W+1)] for _ in range(N)]

for i in range(W+1):
  if i >= W[0]
  Ans[0][i] = V[0]

for i in range(1, N):
  for w in range(W+1):
    if w - W[i] >= 0:
      Ans[i][w] = max(Ans[i-1][w-W[i]], Ans[i-1][w], Ans[i][w])
    else:
      Ans[i][w] = max(Ans[i-1][w], Ans[i][w])

print(max(Ans[N-1]))

Submission status: Runtime Error

Solution code:
N, W = map(int, input().split())
W = []
V = []

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

Ans = [[0 for _ in range(W+1)] for _ in range(N)]

for i in range(W+1):
  if i >= W[0]
  Ans[0][i] = V[0]

for i in range(1, N):
  for w in range(W+1):
    Ans[i][w] = max(Ans[i-1][w-W[i]], Ans[i-1][w])

print(max(Ans[N-1]))

Submission status: Runtime Error

Solution code:
import numpy as np
t=np.zeros([101,10001],dtype=int)
def knapsack(w,val,W,n):
    for i in range(1,n+1):
        for j in range(1,W+1):
            if w[i-1]<=j:
                t[i][j]=max(val[i-1]+t[i-1][j-w[i-1]],t[i-1][j])
            else:
                t[i][j]=t[i-1][j]
    return t[n][W]            
n,W=map(int,input().split())                
w=[]
val=[]
for i in range(0,n):
    a,b=map(int,input().split())
    w.append(a)
    val.append(b)
ans=knapsack(w,val,W,n)
print(ans)

Submission status: Runtime Error

Solution code:
from __future__ import division, print_function
# import threading
# threading.stack_size(2**27)
# import sys
# sys.setrecursionlimit(10**7)
from sys import stdin, stdout
import bisect            #c++ upperbound
import math
import heapq
import numpy as np
i_m=9223372036854775807
def modinv(n,p):
    return pow(n,p-2,p)
def cin():
    return map(int,sin().split())
def ain():                           #takes array as input
    return list(map(int,sin().split()))
def sin():
    return input()
def inin():
    return int(input())
import math  
def GCD(x, y): 
    x=abs(x)
    y=abs(y)
    if(min(x,y)==0):
        return max(x,y)
    while(y): 
        x, y = y, x % y 
    return x 
def Divisors(n) : 
    l = []  
    for i in range(1, int(math.sqrt(n) + 1)) :
        if (n % i == 0) : 
            if (n // i == i) : 
                l.append(i) 
            else : 
                l.append(i)
                l.append(n//i)
    return l
prime=[]
def SieveOfEratosthenes(n): 
    global prime
    prime = [True for i in range(n+1)] 
    p = 2
    while (p * p <= n): 
        if (prime[p] == True): 
            for i in range(p * p, n+1, p): 
                prime[i] = False
        p += 1
    f=[]
    for p in range(2, n): 
        if prime[p]: 
            f.append(p)
    return f
q=[]       
def dfs(n,d,v,c):
    global q
    v[n]=1
    x=d[n]
    q.append(n)
    j=c
    for i in x:
        if i not in v:
            f=dfs(i,d,v,c+1)
            j=max(j,f)
            # print(f)
    return j
    
"""*******************************************************"""
def main():
##    dp = np.full(10**5+1, 10**18, dtype=np.int64)
    n,w=map(int,input().split())
    val=[0]*n
    wt=[0]*n
    dp=[[0 for x in range(w+1)] for x in range(n+1)] 
    for i in range(n):
      a,b=map(int,input().split())
      wt[i]=a
      val[i]=b
    for i in range(1,n+1):
        for j in range(1,w+1):
            if(wt[i-1] <= j):
                dp[i][j]=max(val[i-1] + dp[i-1][j-wt[i-1]] , dp[i-1][j])
            else:
                dp[i][j]=dp[i-1][j]
    print(dp[n][w])
######## Python 2 and 3 footer by Pajenegod and c1729
 
# Note because cf runs old PyPy3 version which doesn't have the sped up
# unicode strings, PyPy3 strings will many times be slower than pypy2.
# There is a way to get around this by using binary strings in PyPy3
# but its syntax is different which makes it kind of a mess to use.
 
# So on cf, use PyPy2 for best string performance.
 
py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange
 
import os, sys
from io import IOBase, BytesIO
 
BUFSIZE = 8192
class FastIO(BytesIO):
    newlines = 0
 
    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = "x" in file.mode or "w" in file.mode
        self.write = super(FastIO, self).write if self.writable else None
 
    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0,2), super(FastIO, self).write(s))[0])
        return s
 
    def read(self):
        while self._fill(): pass
        return super(FastIO,self).read()
 
    def readline(self):
        while self.newlines == 0:
            s = self._fill(); self.newlines = s.count(b"\n") + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.getvalue())
            self.truncate(0), self.seek(0)
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            self.write = lambda s:self.buffer.write(s.encode('ascii'))
            self.read = lambda:self.buffer.read().decode('ascii')
            self.readline = lambda:self.buffer.readline().decode('ascii')
 
 
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip('\r\n')
 
# Cout implemented in Python
import sys
class ostream:
    def __lshift__(self,a):
        sys.stdout.write(str(a))
        return self
cout = ostream()
endl = '\n'
 
# Read all remaining integers in stdin, type is given by optional argument, this is fast
def readnumbers(zero = 0):
    conv = ord if py2 else lambda x:x
    A = []; numb = zero; sign = 1; i = 0; s = sys.stdin.buffer.read()
    try:
        while True:
            if s[i] >= b'R' [0]:
                numb = 10 * numb + conv(s[i]) - 48
            elif s[i] == b'-' [0]: sign = -1
            elif s[i] != b'\r' [0]:
                A.append(sign*numb)
                numb = zero; sign = 1
            i += 1
    except:pass
    if s and s[-1] >= b'R' [0]:
        A.append(sign*numb)
    return A
 
# threading.Thread(target=main).start()
if __name__== "__main__":
  main()

Submission status: Runtime Error

Solution code:


  
  
from __future__ import division, print_function
# import threading
# threading.stack_size(2**27)
# import sys
# sys.setrecursionlimit(10**7)
from sys import stdin, stdout
import bisect            #c++ upperbound
import math
import heapq
import numpy
i_m=9223372036854775807
def modinv(n,p):
    return pow(n,p-2,p)
def cin():
    return map(int,sin().split())
def ain():                           #takes array as input
    return list(map(int,sin().split()))
def sin():
    return input()
def inin():
    return int(input())
import math  
def GCD(x, y): 
    x=abs(x)
    y=abs(y)
    if(min(x,y)==0):
        return max(x,y)
    while(y): 
        x, y = y, x % y 
    return x 
def Divisors(n) : 
    l = []  
    for i in range(1, int(math.sqrt(n) + 1)) :
        if (n % i == 0) : 
            if (n // i == i) : 
                l.append(i) 
            else : 
                l.append(i)
                l.append(n//i)
    return l
prime=[]
def SieveOfEratosthenes(n): 
    global prime
    prime = [True for i in range(n+1)] 
    p = 2
    while (p * p <= n): 
        if (prime[p] == True): 
            for i in range(p * p, n+1, p): 
                prime[i] = False
        p += 1
    f=[]
    for p in range(2, n): 
        if prime[p]: 
            f.append(p)
    return f
q=[]       
def dfs(n,d,v,c):
    global q
    v[n]=1
    x=d[n]
    q.append(n)
    j=c
    for i in x:
        if i not in v:
            f=dfs(i,d,v,c+1)
            j=max(j,f)
            # print(f)
    return j
    
"""*******************************************************"""
def main():
    n,w=map(int,input().split())
    val=[0]*n
    wt=[0]*n
    dp=[[0 for x in range(w+1)] for x in range(n+1)] 
    for i in range(n):
      a,b=map(int,input().split())
      wt[i]=a
      val[i]=b
    for i in range(1,n+1):
        for j in range(1,w+1):
            if(wt[i-1] <= j):
                dp[i][j]=max(val[i-1] + dp[i-1][j-wt[i-1]] , dp[i-1][j])
            else:
                dp[i][j]=dp[i-1][j]
    print(dp[n][w])
######## Python 2 and 3 footer by Pajenegod and c1729
 
# Note because cf runs old PyPy3 version which doesn't have the sped up
# unicode strings, PyPy3 strings will many times be slower than pypy2.
# There is a way to get around this by using binary strings in PyPy3
# but its syntax is different which makes it kind of a mess to use.
 
# So on cf, use PyPy2 for best string performance.
 
py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange
 
import os, sys
from io import IOBase, BytesIO
 
BUFSIZE = 8192
class FastIO(BytesIO):
    newlines = 0
 
    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = "x" in file.mode or "w" in file.mode
        self.write = super(FastIO, self).write if self.writable else None
 
    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0,2), super(FastIO, self).write(s))[0])
        return s
 
    def read(self):
        while self._fill(): pass
        return super(FastIO,self).read()
 
    def readline(self):
        while self.newlines == 0:
            s = self._fill(); self.newlines = s.count(b"\n") + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.getvalue())
            self.truncate(0), self.seek(0)
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            self.write = lambda s:self.buffer.write(s.encode('ascii'))
            self.read = lambda:self.buffer.read().decode('ascii')
            self.readline = lambda:self.buffer.readline().decode('ascii')
 
 
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip('\r\n')
 
# Cout implemented in Python
import sys
class ostream:
    def __lshift__(self,a):
        sys.stdout.write(str(a))
        return self
cout = ostream()
endl = '\n'
 
# Read all remaining integers in stdin, type is given by optional argument, this is fast
def readnumbers(zero = 0):
    conv = ord if py2 else lambda x:x
    A = []; numb = zero; sign = 1; i = 0; s = sys.stdin.buffer.read()
    try:
        while True:
            if s[i] >= b'R' [0]:
                numb = 10 * numb + conv(s[i]) - 48
            elif s[i] == b'-' [0]: sign = -1
            elif s[i] != b'\r' [0]:
                A.append(sign*numb)
                numb = zero; sign = 1
            i += 1
    except:pass
    if s and s[-1] >= b'R' [0]:
        A.append(sign*numb)
    return A
 
# threading.Thread(target=main).start()
if __name__== "__main__":
  main()