Buggy python submission (verdict: Runtime Error):

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

w = [0 for i in range(N+1)]
v = [0 for i in range(N+1)]
Wsum = [0 for i in range(N+1)]
Vsum = [0 for i in range(N+1)]

#品物、重み→1〜N番目
for i in range(N):
    w[i+1],v[i+1] = map(int, input().split())

for i in range(N):
    Wsum[i+1] = Wsum[i] + w[i+1]
    Vsum[i+1] = Vsum[i] + v[i+1]

#i番目の品物まで含み制約W2のナップサック問題の最適解
def nap(i,W2):
    #品物0個のときは価値は0
    if i == 0:
        return 0
    #制約0のときも価値は0
    if W == 0:
        return 0
    #w[i]がW2を超えるときはi番目の品物は不必要
    if W2 < w[i]:
        return nap(i-1,W2)
    #品物の重さ全部足して制約以下なら全部足したものが価値で良い
    if Wsum[i] <= W2:
        return Vsum[i]
        
    #i番目の品物をナップサックに入れるか入れないか
    return max( nap(i-1,W2-w[i])+v[i] , nap(i-1,W2) )
    
            
print(nap(N,W), flush = True))


Fixed submission:

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

w = [0 for i in range(N)]
v = [0 for i in range(N)]
Wsum = [0 for i in range(N+1)]
Vsum = [0 for i in range(N+1)]

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

w.insert(0,"0")
v.insert(0,"0")


for i in range(N):
    Wsum[i+1] = Wsum[i] + w[i+1]
    Vsum[i+1] = Vsum[i] + v[i+1]


nap_memo = {}

#i番目の品物まで含み制約W2のナップサック問題の最適解
def nap(i,W2):
    #重複計算を避けるためnap(i,W2)を保持
    key = str(i) + ':' + str(W2)
    if key in nap_memo:
        return nap_memo[key]
    #品物0個のときは価値は0
    elif i == 0:
        r = 0
    #制約0のときも価値は0
    elif W2 < Wmin:
        r = 0
    #w[i]がW2を超えるときはi番目の品物は不必要
    elif W2 < w[i]:
        r = nap(i-1,W2)
    #品物の重さ全部足して制約以下なら全部足したものが価値で良い
    elif Wsum[i] <= W2:
        r = Vsum[i]
    #i番目の品物をナップサックに入れるか入れないか
    else:
        r = max( nap(i-1,W2-w[i])+v[i] , nap(i-1,W2) )
    
    nap_memo[key] = r
    return r
    
            
print(nap(N,W))

Buggy python submission (verdict: Runtime Error):

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

w = [0 for i in range(N+1)]
v = [0 for i in range(N+1)]
Wsum = [0 for i in range(N+1)]
Vsum = [0 for i in range(N+1)]

#品物、重み→1〜N番目
for i in range(N):
    w[i+1],v[i+1] = map(int, input().split())

for i in range(N):
    Wsum[i+1] = Wsum[i] + w[i+1]
    Vsum[i+1] = Vsum[i] + v[i+1]

#i番目の品物まで含み制約W2のナップサック問題の最適解
def nap(i,W2):
    #品物0個のときは価値は0
    if i == 0:
        return 0
    #制約0のときも価値は0
    if W == 0:
        return 0
    #w[i]がW2を超えるときはi番目の品物は不必要
    if W2 < w[i]:
        return nap(i-1,W2)
    #品物の重さ全部足して制約以下なら全部足したものが価値で良い
    if Wsum[i] <= W2:
        return Vsum[i]
        
    #i番目の品物をナップサックに入れるか入れないか
    return max( nap(i-1,W2-w[i])+v[i] , nap(i-1,W2) )
    
            
print(nap(N,W), flush = True))


Fixed submission:

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

w = [0 for i in range(N)]
v = [0 for i in range(N)]
Wsum = [0 for i in range(N+1)]
Vsum = [0 for i in range(N+1)]

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

w.insert(0,"0")
v.insert(0,"0")


for i in range(N):
    Wsum[i+1] = Wsum[i] + w[i+1]
    Vsum[i+1] = Vsum[i] + v[i+1]


nap_memo = {}

#i番目の品物まで含み制約W2のナップサック問題の最適解
def nap(i,W2):
    #重複計算を避けるためnap(i,W2)を保持
    key = str(i) + ':' + str(W2)
    if key in nap_memo:
        return nap_memo[key]
    #品物0個のときは価値は0
    elif i == 0:
        r = 0
    #制約0のときも価値は0
    elif W2 < Wmin:
        r = 0
    #w[i]がW2を超えるときはi番目の品物は不必要
    elif W2 < w[i]:
        r = nap(i-1,W2)
    #品物の重さ全部足して制約以下なら全部足したものが価値で良い
    elif Wsum[i] <= W2:
        r = Vsum[i]
    #i番目の品物をナップサックに入れるか入れないか
    else:
        r = max( nap(i-1,W2-w[i])+v[i] , nap(i-1,W2) )
    
    nap_memo[key] = r
    return r
    
            
print(nap(N,W))

Buggy python submission (verdict: Time Limit Exceeded):

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

wv = [[0 for i in range(2)] for j in range(N+1)]
Wsum = [0 for i in range(N+1)]
Vsum = [0 for i in range(N+1)]

for i in range(N):
    wv[i+1][0],wv[i+1][1] = map(int, input().split())

wv.sort()

for i in range(N):
    Wsum[i+1] = Wsum[i] + wv[i+1][0]
    Vsum[i+1] = Vsum[i] + wv[i+1][1]

#i番目の品物まで含み制約W2のナップサック問題の最適解
def nap(i,W2):
    #品物0個のときはもちろん価値は0
    if i == 0:
        return 0
    #制約が0のときも価値は0
    if W2 == 0:
        return 0
    #w[i]がW2を超えるときはi番目の品物は入れられない
    if W2 < wv[i][0]:
        return nap(i-1,W2)
    #品物の重さ全部足して制約以下なら全部足したものが価値
    if Wsum[i] <= W2:
        return Vsum[i]

    return max( nap(i-1,W2-wv[i][0])+wv[i][1] , nap(i-1,W2) )
    
            
print(nap(N,W))


Fixed submission:

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

w = [0 for i in range(N)]
v = [0 for i in range(N)]
Wsum = [0 for i in range(N+1)]
Vsum = [0 for i in range(N+1)]

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

w.insert(0,"0")
v.insert(0,"0")


for i in range(N):
    Wsum[i+1] = Wsum[i] + w[i+1]
    Vsum[i+1] = Vsum[i] + v[i+1]


nap_memo = {}

#i番目の品物まで含み制約W2のナップサック問題の最適解
def nap(i,W2):
    #重複計算を避けるためnap(i,W2)を保持
    key = str(i) + ':' + str(W2)
    if key in nap_memo:
        return nap_memo[key]
    #品物0個のときは価値は0
    elif i == 0:
        r = 0
    #制約0のときも価値は0
    elif W2 < Wmin:
        r = 0
    #w[i]がW2を超えるときはi番目の品物は不必要
    elif W2 < w[i]:
        r = nap(i-1,W2)
    #品物の重さ全部足して制約以下なら全部足したものが価値で良い
    elif Wsum[i] <= W2:
        r = Vsum[i]
    #i番目の品物をナップサックに入れるか入れないか
    else:
        r = max( nap(i-1,W2-w[i])+v[i] , nap(i-1,W2) )
    
    nap_memo[key] = r
    return r
    
            
print(nap(N,W))

Buggy python submission (verdict: Time Limit Exceeded):

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

wv = [[0 for i in range(2)] for j in range(N+1)]
Wsum = [0 for i in range(N+1)]
Vsum = [0 for i in range(N+1)]

for i in range(N):
    wv[i+1][0],wv[i+1][1] = map(int, input().split())

sorted(wv)

for i in range(N):
    Wsum[i+1] = Wsum[i] + wv[i+1][0]
    Vsum[i+1] = Vsum[i] + wv[i+1][1]

#i番目の品物まで含み制約W2のナップサック問題の最適解
def nap(i,W2):
    #品物0個のときはもちろん価値は0
    if i == 0:
        return 0
    #制約が0のときも価値は0
    if W2 == 0:
        return 0
    #w[i]がW2を超えるときはi番目の品物は入れられない
    if W2 < wv[i][0]:
        return nap(i-1,W2)
    #品物の重さ全部足して制約以下なら全部足したものが価値
    if Wsum[i] <= W2:
        return Vsum[i]

    return max( nap(i-1,W2-wv[i][0])+wv[i][1] , nap(i-1,W2) )
    
            
print(nap(N,W))


Fixed submission:

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

w = [0 for i in range(N)]
v = [0 for i in range(N)]
Wsum = [0 for i in range(N+1)]
Vsum = [0 for i in range(N+1)]

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

w.insert(0,"0")
v.insert(0,"0")


for i in range(N):
    Wsum[i+1] = Wsum[i] + w[i+1]
    Vsum[i+1] = Vsum[i] + v[i+1]


nap_memo = {}

#i番目の品物まで含み制約W2のナップサック問題の最適解
def nap(i,W2):
    #重複計算を避けるためnap(i,W2)を保持
    key = str(i) + ':' + str(W2)
    if key in nap_memo:
        return nap_memo[key]
    #品物0個のときは価値は0
    elif i == 0:
        r = 0
    #制約0のときも価値は0
    elif W2 < Wmin:
        r = 0
    #w[i]がW2を超えるときはi番目の品物は不必要
    elif W2 < w[i]:
        r = nap(i-1,W2)
    #品物の重さ全部足して制約以下なら全部足したものが価値で良い
    elif Wsum[i] <= W2:
        r = Vsum[i]
    #i番目の品物をナップサックに入れるか入れないか
    else:
        r = max( nap(i-1,W2-w[i])+v[i] , nap(i-1,W2) )
    
    nap_memo[key] = r
    return r
    
            
print(nap(N,W))

Buggy python submission (verdict: Time Limit Exceeded):

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

wv = [[0 for i in range(2)] for j in range(N+1)]
Wsum = [0 for i in range(N+1)]
Vsum = [0 for i in range(N+1)]

for i in range(N):
    wv[i+1][0],wv[i+1][1] = map(int, input().split())

sorted(wv)

for i in range(N):
    Wsum[i+1] = Wsum[i] + wv[i+1][0]
    Vsum[i+1] = Vsum[i] + wv[i+1][1]

#i番目の品物まで含み制約W2のナップサック問題の最適解
def nap(i,W2):
    #品物0個のときはもちろん価値は0
    if i == 0:
        return 0
    #w[i]がW2を超えるときはi番目の品物は不必要
    if W2 < wv[i][0]:
        return nap(i-1,W2)
    #品物の重さ全部足して制約以下なら全部足したものが価値
    if Wsum[i] <= W2:
        return Vsum[i]

    return max( nap(i-1,W2-wv[i][0])+wv[i][1] , nap(i-1,W2) )
    
            
print(nap(N,W))


Fixed submission:

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

w = [0 for i in range(N)]
v = [0 for i in range(N)]
Wsum = [0 for i in range(N+1)]
Vsum = [0 for i in range(N+1)]

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

w.insert(0,"0")
v.insert(0,"0")


for i in range(N):
    Wsum[i+1] = Wsum[i] + w[i+1]
    Vsum[i+1] = Vsum[i] + v[i+1]


nap_memo = {}

#i番目の品物まで含み制約W2のナップサック問題の最適解
def nap(i,W2):
    #重複計算を避けるためnap(i,W2)を保持
    key = str(i) + ':' + str(W2)
    if key in nap_memo:
        return nap_memo[key]
    #品物0個のときは価値は0
    elif i == 0:
        r = 0
    #制約0のときも価値は0
    elif W2 < Wmin:
        r = 0
    #w[i]がW2を超えるときはi番目の品物は不必要
    elif W2 < w[i]:
        r = nap(i-1,W2)
    #品物の重さ全部足して制約以下なら全部足したものが価値で良い
    elif Wsum[i] <= W2:
        r = Vsum[i]
    #i番目の品物をナップサックに入れるか入れないか
    else:
        r = max( nap(i-1,W2-w[i])+v[i] , nap(i-1,W2) )
    
    nap_memo[key] = r
    return r
    
            
print(nap(N,W))

Buggy python submission (verdict: Time Limit Exceeded):

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

w = [0 for i in range(N+1)]
v = [0 for i in range(N+1)]
Wsum = [0 for i in range(N+1)]
Vsum = [0 for i in range(N+1)]

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

for i in range(N):
    Wsum[i+1] = Wsum[i] + w[i+1]
    Vsum[i+1] = Vsum[i] + v[i+1]

#i番目の品物まで含み制約W2のナップサック問題の最適解
def nap(i,W2):
    #品物0個のときはもちろん価値は0
    if i == 0:
        return 0
    #w[i]がW2を超えるときはi番目の品物は不必要
    if W2 < w[i]:
        return nap(i-1,W2)
    #品物１つで制約OK→品物一つの価値がnapの価値        
    if i == 1:
        return v[i]
    #品物の重さ全部足して制約以下なら全部足したものが価値
    if Wsum[i] <= W2:
        return Vsum[i]

    return max( nap(i-1,W2-w[i])+v[i] , nap(i-1,W2) )
    
            
print(nap(N,W))


Fixed submission:

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

w = [0 for i in range(N)]
v = [0 for i in range(N)]
Wsum = [0 for i in range(N+1)]
Vsum = [0 for i in range(N+1)]

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

w.insert(0,"0")
v.insert(0,"0")


for i in range(N):
    Wsum[i+1] = Wsum[i] + w[i+1]
    Vsum[i+1] = Vsum[i] + v[i+1]


nap_memo = {}

#i番目の品物まで含み制約W2のナップサック問題の最適解
def nap(i,W2):
    #重複計算を避けるためnap(i,W2)を保持
    key = str(i) + ':' + str(W2)
    if key in nap_memo:
        return nap_memo[key]
    #品物0個のときは価値は0
    elif i == 0:
        r = 0
    #制約0のときも価値は0
    elif W2 < Wmin:
        r = 0
    #w[i]がW2を超えるときはi番目の品物は不必要
    elif W2 < w[i]:
        r = nap(i-1,W2)
    #品物の重さ全部足して制約以下なら全部足したものが価値で良い
    elif Wsum[i] <= W2:
        r = Vsum[i]
    #i番目の品物をナップサックに入れるか入れないか
    else:
        r = max( nap(i-1,W2-w[i])+v[i] , nap(i-1,W2) )
    
    nap_memo[key] = r
    return r
    
            
print(nap(N,W))

Buggy python submission (verdict: Time Limit Exceeded):

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

w = [0 for i in range(N+1)]
v = [0 for i in range(N+1)]
Wsum = [0 for i in range(N+1)]
Vsum = [0 for i in range(N+1)]

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

for i in range(N):
    Wsum[i+1] = Wsum[i] + w[i+1]
    Vsum[i+1] = Vsum[i] + v[i+1]

#i番目の品物まで含み制約W2のナップサック問題の最適解
def nap(i,W2):
    #品物0個のときはもちろん価値は0
    if i == 0:
        return 0
    #w[i]がW2を超えるときはi番目の品物は不必要
    if W2 < w[i]:
        return nap(i-1,W2)
    #品物１つで制約OK→品物一つの価値がnapの価値        
    if i == 1:
        return v[i]
    #品物の重さ全部足して制約以下なら全部足したものが価値
    if Wsum[i] < W2:
        return Vsum[i]

    return max( nap(i-1,W2-w[i])+v[i] , nap(i-1,W2) )
    
            
print(nap(N,W))


Fixed submission:

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

w = [0 for i in range(N)]
v = [0 for i in range(N)]
Wsum = [0 for i in range(N+1)]
Vsum = [0 for i in range(N+1)]

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

w.insert(0,"0")
v.insert(0,"0")


for i in range(N):
    Wsum[i+1] = Wsum[i] + w[i+1]
    Vsum[i+1] = Vsum[i] + v[i+1]


nap_memo = {}

#i番目の品物まで含み制約W2のナップサック問題の最適解
def nap(i,W2):
    #重複計算を避けるためnap(i,W2)を保持
    key = str(i) + ':' + str(W2)
    if key in nap_memo:
        return nap_memo[key]
    #品物0個のときは価値は0
    elif i == 0:
        r = 0
    #制約0のときも価値は0
    elif W2 < Wmin:
        r = 0
    #w[i]がW2を超えるときはi番目の品物は不必要
    elif W2 < w[i]:
        r = nap(i-1,W2)
    #品物の重さ全部足して制約以下なら全部足したものが価値で良い
    elif Wsum[i] <= W2:
        r = Vsum[i]
    #i番目の品物をナップサックに入れるか入れないか
    else:
        r = max( nap(i-1,W2-w[i])+v[i] , nap(i-1,W2) )
    
    nap_memo[key] = r
    return r
    
            
print(nap(N,W))

Buggy python submission (verdict: Time Limit Exceeded):

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

w = [0 for i in range(N+1)]
v = [0 for i in range(N+1)]

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

#i番目の品物まで含み制約W2のナップサック問題の最適解
def nap(i,W2):
    #品物0個のときはもちろん価値は0
    if i == 0:
        return 0
    #w[i]がW2を超えるときはi番目の品物は不必要
    if W2 < w[i]:
        return nap(i-1,W2)
    W3 = 0
    for j in range(i):
        W3 = W3 + w[j+1]
    if W3 < W2:
        V3 = 0
        for j in range(i):
            V3 = V3 + v[j+1]
        return V3
    #品物１つで制約OK→品物一つの価値がnapの価値        
    if i == 1:
        return v[i]

    return max( nap(i-1,W2-w[i])+v[i] , nap(i-1,W2) )
    
            
print(nap(N,W))


Fixed submission:

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

w = [0 for i in range(N)]
v = [0 for i in range(N)]
Wsum = [0 for i in range(N+1)]
Vsum = [0 for i in range(N+1)]

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

w.insert(0,"0")
v.insert(0,"0")


for i in range(N):
    Wsum[i+1] = Wsum[i] + w[i+1]
    Vsum[i+1] = Vsum[i] + v[i+1]


nap_memo = {}

#i番目の品物まで含み制約W2のナップサック問題の最適解
def nap(i,W2):
    #重複計算を避けるためnap(i,W2)を保持
    key = str(i) + ':' + str(W2)
    if key in nap_memo:
        return nap_memo[key]
    #品物0個のときは価値は0
    elif i == 0:
        r = 0
    #制約0のときも価値は0
    elif W2 < Wmin:
        r = 0
    #w[i]がW2を超えるときはi番目の品物は不必要
    elif W2 < w[i]:
        r = nap(i-1,W2)
    #品物の重さ全部足して制約以下なら全部足したものが価値で良い
    elif Wsum[i] <= W2:
        r = Vsum[i]
    #i番目の品物をナップサックに入れるか入れないか
    else:
        r = max( nap(i-1,W2-w[i])+v[i] , nap(i-1,W2) )
    
    nap_memo[key] = r
    return r
    
            
print(nap(N,W))

Buggy python submission (verdict: Time Limit Exceeded):

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

w = [0 for i in range(N+1)]
v = [0 for i in range(N+1)]

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

#i番目の品物まで含み制約W2のナップサック問題の最適解
def nap(i,W2):
    #品物0個のときはもちろん価値は0
    if i == 0:
        return 0
    #w[i]がW2を超えるときはi番目の品物は不必要
    if W2 < w[i]:
        return nap(i-1,W2)
    #品物１つで制約OK→品物一つの価値がnapの価値        
    if i == 1:
        return v[i]

    return max( nap(i-1,W2-w[i])+v[i] , nap(i-1,W2) )
    
            
print(nap(N,W))


Fixed submission:

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

w = [0 for i in range(N)]
v = [0 for i in range(N)]
Wsum = [0 for i in range(N+1)]
Vsum = [0 for i in range(N+1)]

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

w.insert(0,"0")
v.insert(0,"0")


for i in range(N):
    Wsum[i+1] = Wsum[i] + w[i+1]
    Vsum[i+1] = Vsum[i] + v[i+1]


nap_memo = {}

#i番目の品物まで含み制約W2のナップサック問題の最適解
def nap(i,W2):
    #重複計算を避けるためnap(i,W2)を保持
    key = str(i) + ':' + str(W2)
    if key in nap_memo:
        return nap_memo[key]
    #品物0個のときは価値は0
    elif i == 0:
        r = 0
    #制約0のときも価値は0
    elif W2 < Wmin:
        r = 0
    #w[i]がW2を超えるときはi番目の品物は不必要
    elif W2 < w[i]:
        r = nap(i-1,W2)
    #品物の重さ全部足して制約以下なら全部足したものが価値で良い
    elif Wsum[i] <= W2:
        r = Vsum[i]
    #i番目の品物をナップサックに入れるか入れないか
    else:
        r = max( nap(i-1,W2-w[i])+v[i] , nap(i-1,W2) )
    
    nap_memo[key] = r
    return r
    
            
print(nap(N,W))

Buggy python submission (verdict: Time Limit Exceeded):

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

w = [0]*N
v = [0]*N
Vmax = [[0 for i in range(W+1)] for j in range(N+1)]

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


# i個目の品物を追加
for i in range(N):
    for j in range(W+1):
        if j<w[i]:
            Vmax[i+1][j] = Vmax[i][j]
            continue        
        if Vmax[i][j-w[i]] + v[i] <= Vmax[i][j]:
            Vmax[i+1][j] = Vmax[i][j]
            continue
        else:
            Vmax[i+1][j] = Vmax[i][j-w[i]] + v[i]      


            
print(Vmax[N][W])


Fixed submission:

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

w = [0 for i in range(N)]
v = [0 for i in range(N)]
Wsum = [0 for i in range(N+1)]
Vsum = [0 for i in range(N+1)]

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

w.insert(0,"0")
v.insert(0,"0")


for i in range(N):
    Wsum[i+1] = Wsum[i] + w[i+1]
    Vsum[i+1] = Vsum[i] + v[i+1]


nap_memo = {}

#i番目の品物まで含み制約W2のナップサック問題の最適解
def nap(i,W2):
    #重複計算を避けるためnap(i,W2)を保持
    key = str(i) + ':' + str(W2)
    if key in nap_memo:
        return nap_memo[key]
    #品物0個のときは価値は0
    elif i == 0:
        r = 0
    #制約0のときも価値は0
    elif W2 < Wmin:
        r = 0
    #w[i]がW2を超えるときはi番目の品物は不必要
    elif W2 < w[i]:
        r = nap(i-1,W2)
    #品物の重さ全部足して制約以下なら全部足したものが価値で良い
    elif Wsum[i] <= W2:
        r = Vsum[i]
    #i番目の品物をナップサックに入れるか入れないか
    else:
        r = max( nap(i-1,W2-w[i])+v[i] , nap(i-1,W2) )
    
    nap_memo[key] = r
    return r
    
            
print(nap(N,W))

Buggy python submission (verdict: Time Limit Exceeded):

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

w = [0]*N
v = [0]*N
Vmax = [[0 for i in range(W+1)] for j in range(N+1)]

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


# i個目の品物を追加
for i in range(N):
    for j in range(W+1):
        Vmax[i+1][j] = Vmax[i][j]
        
        if j<w[i]:
            Vmax[i+1][j] = Vmax[i][j]
            continue
        
        if Vmax[i][j-w[i]] + v[i] > Vmax[i][j]:
            Vmax[i+1][j] = Vmax[i][j-w[i]] + v[i]
        else:
            Vmax[i+1][j] = Vmax[i+1][j]
            
    

            
print(Vmax[N][W])
            
    
    


Fixed submission:

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

w = [0 for i in range(N)]
v = [0 for i in range(N)]
Wsum = [0 for i in range(N+1)]
Vsum = [0 for i in range(N+1)]

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

w.insert(0,"0")
v.insert(0,"0")


for i in range(N):
    Wsum[i+1] = Wsum[i] + w[i+1]
    Vsum[i+1] = Vsum[i] + v[i+1]


nap_memo = {}

#i番目の品物まで含み制約W2のナップサック問題の最適解
def nap(i,W2):
    #重複計算を避けるためnap(i,W2)を保持
    key = str(i) + ':' + str(W2)
    if key in nap_memo:
        return nap_memo[key]
    #品物0個のときは価値は0
    elif i == 0:
        r = 0
    #制約0のときも価値は0
    elif W2 < Wmin:
        r = 0
    #w[i]がW2を超えるときはi番目の品物は不必要
    elif W2 < w[i]:
        r = nap(i-1,W2)
    #品物の重さ全部足して制約以下なら全部足したものが価値で良い
    elif Wsum[i] <= W2:
        r = Vsum[i]
    #i番目の品物をナップサックに入れるか入れないか
    else:
        r = max( nap(i-1,W2-w[i])+v[i] , nap(i-1,W2) )
    
    nap_memo[key] = r
    return r
    
            
print(nap(N,W))