Buggy python submission (verdict: Time Limit Exceeded):
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
#品物は0～N-1と考えるので注意！

DP = [[-1]*(W+1) for _ in range(N-1)] #0~N-2
#DP[depth:0~N-1][0~W] calc()の結果をメモる
#DP[N-1][]については、W-pwsum>=N-1の重さならN-1の重さ
##W-pwsum<N-1の重さ なら 0
##→W-(N-1)>=pwsumとW-(N-1)<pwsumで場合分け
DP.append([0]*(W+1))
tmppwsum = 0
weiofMinus1, valofNminus1 = wv[N-1]
while W-weiofMinus1>=tmppwsum:
  DP[N-1][tmppwsum] = valofNminus1
  tmppwsum += 1


#合計pwsumの重さを入れた状態で、
#depth以降の品物を選ぶ場合の最大価値を返す関数
def calc(depth, pwsum):
  #メモ済みだったらメモした値を返す
  dp =  DP[depth][pwsum]
  if dp != -1: return dp
  
  nowWei, nowVal = wv[depth] #今選んでる品物のこと
  if pwsum + nowWei > W:
    #入れると重さ超過なので、入れずに次を考える
#    if depth >= N-1:
#      #今の品物が最後なら、以降得られる価値は0
#      DP[depth][pwsum] = 0
#      return 0
#    else:
    #次の品物が無い場合はDPで省かれている
      #次の品物がある場合、今のを入れずに次へいく
    irenai = calc(depth+1, pwsum)
    DP[depth][pwsum] = irenai
    return irenai
  if pwsum + nowWei <= W:
    #入れても大丈夫な場合
#    if depth >= N-1:
#      #今の品物が最後なら、今の品物しか入れられない
#      DP[depth][pwsum] = nowVal
#      return nowVal
    #次の品物が無い場合はDPで省かれている
      #次の品物がある場合、今のを入れる入れないの2択
    ireru = nowVal + calc(depth+1, pwsum+nowWei)
    irenai = calc(depth+1, pwsum)
    ans = max(ireru, irenai)
    DP[depth][pwsum] = ans
    return ans
    
print(calc(0, 0))

Fixed submission:
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
#品物は0～N-1と考えるので注意！

DP = [0]*(W+1) #0~W
#各iにつき、残り重さがWの時の最大価値をDPに入れる


#i=N-1までいった時のmax(DP)が答え
for i in range(0, N, 1): #0~N-1
  w, v = wv[i]
  #残りwei(W-DPの2個目の添字)がw未満の場合入れられない
  #入れない場合は変えなければいい
  for nw in range(W, w-1, -1):
    iretaV = DP[nw-w] + v
    if iretaV > DP[nw]:
      DP[nw] = iretaV

print(max(DP))

Buggy python submission (verdict: Time Limit Exceeded):
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
#品物は0～N-1と考えるので注意！

DP = [[-1]*(W+1) for _ in range(N-1)] #0~N-2
#DP[depth:0~N-1][0~W] calc()の結果をメモる
#DP[N-1][]については、W-pwsum>=N-1の重さならN-1の重さ
##W-pwsum<N-1の重さ なら 0
##→W-(N-1)>=pwsumとW-(N-1)<pwsumで場合分け
DP.append([0]*(W+1))
tmppwsum = 0
weiofMinus1, valofNminus1 = wv[N-1]
while W-weiofMinus1>=tmppwsum:
  DP[N-1][tmppwsum] = valofNminus1
  tmppwsum += 1


#合計pwsumの重さを入れた状態で、
#depth以降の品物を選ぶ場合の最大価値を返す関数
def calc(depth, pwsum):
  #メモ済みだったらメモした値を返す
  dp =  DP[depth][pwsum]
  if dp != -1: return dp
  
  nowWei, nowVal = wv[depth] #今選んでる品物のこと
  if pwsum + nowWei > W:
    #入れると重さ超過なので、入れずに次を考える
#    if depth >= N-1:
#      #今の品物が最後なら、以降得られる価値は0
#      DP[depth][pwsum] = 0
#      return 0
#    else:
    #次の品物が無い場合はDPで省かれている
      #次の品物がある場合、今のを入れずに次へいく
    irenai = calc(depth+1, pwsum)
    DP[depth][pwsum] = irenai
    return irenai
  if pwsum + nowWei <= W:
    #入れても大丈夫な場合
#    if depth >= N-1:
#      #今の品物が最後なら、今の品物しか入れられない
#      DP[depth][pwsum] = nowVal
#      return nowVal
    #次の品物が無い場合はDPで省かれている
      #次の品物がある場合、今のを入れる入れないの2択
    ireru = nowVal + calc(depth+1, pwsum+nowWei)
    irenai = calc(depth+1, pwsum)
    DP[depth][pwsum] = max(ireru, irenai)
    return max(ireru, irenai)
    
print(calc(0, 0))

Fixed submission:
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
#品物は0～N-1と考えるので注意！

DP = [0]*(W+1) #0~W
#各iにつき、残り重さがWの時の最大価値をDPに入れる


#i=N-1までいった時のmax(DP)が答え
for i in range(0, N, 1): #0~N-1
  w, v = wv[i]
  #残りwei(W-DPの2個目の添字)がw未満の場合入れられない
  #入れない場合は変えなければいい
  for nw in range(W, w-1, -1):
    iretaV = DP[nw-w] + v
    if iretaV > DP[nw]:
      DP[nw] = iretaV

print(max(DP))

Buggy python submission (verdict: Time Limit Exceeded):
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
#品物は0～N-1と考えるので注意！

DP = [[-1]*(W+1) for _ in range(N-1)] #0~N-2
#DP[depth:0~N-1][0~W] calc()の結果をメモる
#DP[N-1][]については、W-pwsum>=N-1の重さならN-1の重さ
##W-pwsum<N-1の重さ なら 0
##→W-(N-1)>=pwsumとW-(N-1)<pwsumで場合分け
DP.append([0]*(W+1))
tmppwsum = 0
weiofMinus1, valofNminus1 = wv[N-1]
while W-weiofMinus1>=tmppwsum:
  DP[N-1][tmppwsum] = valofNminus1
  tmppwsum += 1


#合計pwsumの重さを入れた状態で、
#depth以降の品物を選ぶ場合の最大価値を返す関数
def calc(depth, pwsum):
  #メモ済みだったらメモした値を返す
  dp =  DP[depth][pwsum]
  if dp != -1: return dp
  
  nowWei, nowVal = wv[depth] #今選んでる品物のこと
  if pwsum + nowWei > W:
    #入れると重さ超過なので、入れずに次を考える
#    if depth >= N-1:
#      #今の品物が最後なら、以降得られる価値は0
#      DP[depth][pwsum] = 0
#      return 0
#    else:
    #次の品物が無い場合はDPで省かれている
      #次の品物がある場合、今のを入れずに次へいく
    irenai = calc(depth+1, pwsum)
    DP[depth][pwsum] = irenai
    return irenai
  if pwsum + nowWei <= W:
    #入れても大丈夫な場合
#    if depth >= N-1:
#      #今の品物が最後なら、今の品物しか入れられない
#      DP[depth][pwsum] = nowVal
#      return nowVal
    #次の品物が無い場合はDPで省かれている
      #次の品物がある場合、今のを入れる入れないの2択
    ireru = nowVal + calc(depth+1, pwsum+nowWei)
    irenai = calc(depth+1, pwsum)
    DP[depth][pwsum] = max(ireru, irenai)
    return max(ireru, irenai)
    
print(calc(0, 0))

Fixed submission:
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
#品物は0～N-1と考えるので注意！

DP = [0]*(W+1) #0~W
#各iにつき、残り重さがWの時の最大価値をDPに入れる


#i=N-1までいった時のmax(DP)が答え
for i in range(0, N, 1): #0~N-1
  w, v = wv[i]
  #残りwei(W-DPの2個目の添字)がw未満の場合入れられない
  #入れない場合は変えなければいい
  for nw in range(W, w-1, -1):
    iretaV = DP[nw-w] + v
    if iretaV > DP[nw]:
      DP[nw] = iretaV

print(max(DP))

Buggy python submission (verdict: Time Limit Exceeded):
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
#品物は0～N-1と考えるので注意！

DP = [[-1]*(W+1) for _ in range(N)]
#DP[depth:0~N-1][0~W] calc()の結果をメモる

#合計pwsumの重さを入れた状態で、
#depth以降の品物を選ぶ場合の最大価値を返す関数
def calc(depth, pwsum):
  #メモ済みだったらメモした値を返す
  dp =  DP[depth][pwsum]
  if dp != -1: return dp
  
  nowWei, nowVal = wv[depth] #今選んでる品物のこと
  if pwsum + nowWei > W:
    #入れると重さ超過なので、入れずに次を考える
    if depth >= N-1:
      #今の品物が最後なら、以降得られる価値は0
      DP[depth][pwsum] = 0
      return 0
    else:
      #次の品物がある場合、今のを入れずに次へいく
      irenai = calc(depth+1, pwsum)
      DP[depth][pwsum] = irenai
      return irenai
  if pwsum + nowWei <= W:
    #入れても大丈夫な場合
    if depth >= N-1:
      #今の品物が最後なら、今の品物しか入れられない
      DP[depth][pwsum] = nowVal
      return nowVal
    else:
      #次の品物がある場合、今のを入れる入れないの2択
      ireru = nowVal + calc(depth+1, pwsum+nowWei)
      irenai = calc(depth+1, pwsum)
      DP[depth][pwsum] = max(ireru, irenai)
      return max(ireru, irenai)
    
print(calc(0, 0))

Fixed submission:
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
#品物は0～N-1と考えるので注意！

DP = [0]*(W+1) #0~W
#各iにつき、残り重さがWの時の最大価値をDPに入れる


#i=N-1までいった時のmax(DP)が答え
for i in range(0, N, 1): #0~N-1
  w, v = wv[i]
  #残りwei(W-DPの2個目の添字)がw未満の場合入れられない
  #入れない場合は変えなければいい
  for nw in range(W, w-1, -1):
    iretaV = DP[nw-w] + v
    if iretaV > DP[nw]:
      DP[nw] = iretaV

print(max(DP))

Buggy python submission (verdict: Time Limit Exceeded):
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
#品物は0～N-1と考えるので注意！

#合計pwsumの重さ、合計pvsumの価値を入れた状態で、
#depth以降の品物を選ぶ場合の最大価値を返す関数
def calc(depth, pwsum, pvsum):
  nowWei, nowVal = wv[depth] #今選んでる品物のこと
  if pwsum + nowWei > W:
    #入れると重さ超過なので、入れずに次を考える
    if depth >= N-1: return pvsum
      #今の品物が最後なら、そのまま返す
    else:
      #次の品物がある場合、今のを入れずに次へいく
      irenai = calc(depth+1, pwsum, pvsum)
      return irenai
  if pwsum + nowWei <= W:
    #入れても大丈夫な場合
    if depth >= N-1: return pvsum+nowVal
      #今の品物が最後なら、今の品物を入れて返す
    else:
      #次の品物がある場合、今のを入れる入れないの2択
      ireru = calc(depth+1, pwsum+nowWei, pvsum+nowVal)
      irenai = calc(depth+1, pwsum, pvsum)
      return max(ireru, irenai)
    
print(calc(0, 0, 0))

Fixed submission:
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
#品物は0～N-1と考えるので注意！

DP = [0]*(W+1) #0~W
#各iにつき、残り重さがWの時の最大価値をDPに入れる


#i=N-1までいった時のmax(DP)が答え
for i in range(0, N, 1): #0~N-1
  w, v = wv[i]
  #残りwei(W-DPの2個目の添字)がw未満の場合入れられない
  #入れない場合は変えなければいい
  for nw in range(W, w-1, -1):
    iretaV = DP[nw-w] + v
    if iretaV > DP[nw]:
      DP[nw] = iretaV

print(max(DP))