Buggy python submission (verdict: Time Limit Exceeded):
N,W=map(int,input().split())
w=[]
v=[]
maxV=0
for i in range(N):
    a,b=map(int,input().split())
    if maxV<b:
        maxV=b
    w.append(a)
    v.append(b)
#dp[n個目のアイテムまでで][V以上を達成する]=最小のw
#dp[0][v]=inf ゼロ個でｖは無理なので
#dp[0][0]=0と初期化する
#だからiの時dp[i][v]=min(dp[i-1][v],dp[i-1][V-v[i-1]]+w[i])である<-i-1なのはvとかにはゼロ個とかないので
#V-v[i]<0ならば、とれないので前者になるね！！
#これをi=0(は初期化でする)->nまでおこない、各iについてはとりうる最大のValueを考えるが
#これは最大で各アイテムについて最大のVがあってこれにアイテム数Nを掛けたものである
#つまりdpのサイズはdp[0->N][0->maxV*N]をとればよい

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

for i in range(1,N+1):
    for val in range(maxV*N+1):
        tmp1=dp[i-1][val]#とらない
        if val-v[i-1]<0:#この時、iこめの価値がおおきいので、これをとるだけで達成してしまう
            tmp2=w[i-1]#i=1の時、dp[0][val]=inf
        else:#i=1の時val-v[0]>0で無限になるので
            tmp2=dp[i-1][val-v[i-1]]+w[i-1]#
        res=min(tmp1,tmp2)
        dp[i][val]=res
#ここでW以下となるvalの最大値をたんさくする
max=0
for value in range(len(dp[N])):
    if dp[N][value]<=W:
        if value>max:
            max=value
print(max)


Fixed submission:
def knap(N,W,weight,value):
    inf=float("inf")
    dp=[[-inf for i in range(W+1)] for j in range(N+1)]
    #各nについて初期化　以下で各ｗについて0この時０とする
    for i in range(W+1):#w+1とは0~w
        dp[0][i]=0
    for i in range(N):#each n 0~N-1
        for w in range(W+1):#w 0~w
            if weight[i]<=w:#=を入れないとぎりぎりの時が困る
                dp[i+1][w]=max(dp[i][w-weight[i]]+value[i],dp[i][w])
            else:
                dp[i+1][w]=dp[i][w]
   # print(dp)
    return dp[N][W]


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)
print(knap(n,W,w,v))

Buggy python submission (verdict: Time Limit Exceeded):
N,W=map(int,input().split())
w=[]
v=[]
maxV=0
for i in range(N):
    a,b=map(int,input().split())
    if maxV<b:
        maxV=b
    w.append(a)
    v.append(b)
#dp[n個目のアイテムまでで][V以上を達成する]=最小のw
#dp[0][v]=inf ゼロ個でｖは無理なので
#dp[0][0]=0と初期化する
#だからiの時dp[i][v]=min(dp[i-1][v],dp[i-1][V-v[i-1]]+w[i])である<-i-1なのはvとかにはゼロ個とかないので
#V-v[i]<0ならば、とれないので前者になるね！！
#これをi=0(は初期化でする)->nまでおこない、各iについてはとりうる最大のValueを考えるが
#これは最大で各アイテムについて最大のVがあってこれにアイテム数Nを掛けたものである
#つまりdpのサイズはdp[0->N][0->maxV*N]をとればよい

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

for i in range(1,N+1):
    for val in range(maxV*N+1):
        tmp1=dp[i-1][val]#とらない
        if val-v[i-1]<0:#この時、iこめの価値がおおきいので、これをとるだけで達成してしまう
            tmp2=w[i-1]#i=1の時、dp[0][val]=inf
        else:#i=1の時val-v[0]>0で無限になるので
            tmp2=dp[i-1][val-v[i-1]]+w[i-1]#
        res=min(tmp1,tmp2)
        dp[i][val]=res
#ここでW以下となるvalの最大値をたんさくする
max=0
for value in range(len(dp[N])):
    if dp[N][value]<=W:
        if value>max:
            max=value
print(max)


Fixed submission:
def knap(N,W,weight,value):
    inf=float("inf")
    dp=[[-inf for i in range(W+1)] for j in range(N+1)]
    #各nについて初期化　以下で各ｗについて0この時０とする
    for i in range(W+1):#w+1とは0~w
        dp[0][i]=0
    for i in range(N):#each n 0~N-1
        for w in range(W+1):#w 0~w
            if weight[i]<=w:#=を入れないとぎりぎりの時が困る
                dp[i+1][w]=max(dp[i][w-weight[i]]+value[i],dp[i][w])
            else:
                dp[i+1][w]=dp[i][w]
   # print(dp)
    return dp[N][W]


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)
print(knap(n,W,w,v))

Buggy python submission (verdict: Time Limit Exceeded):
N,W=map(int,input().split())
w=[]
v=[]
maxV=0
for i in range(N):
    a,b=map(int,input().split())
    if maxV<b:
        maxV=b
    w.append(a)
    v.append(b)
#dp[n個目のアイテムまでで][V以上を達成する]=最小のw
#dp[0][v]=inf ゼロ個でｖは無理なので
#dp[0][0]=0と初期化する
#だからiの時dp[i][v]=min(dp[i-1][v],dp[i-1][V-v[i-1]]+w[i])である<-i-1なのはvとかにはゼロ個とかないので
#V-v[i]<0ならば、とれないので前者になるね！！
#これをi=0(は初期化でする)->nまでおこない、各iについてはとりうる最大のValueを考えるが
#これは最大で各アイテムについて最大のVがあってこれにアイテム数Nを掛けたものである
#つまりdpのサイズはdp[0->N][0->maxV*N]をとればよい

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

for i in range(1,N+1):
    for val in range(maxV*N+1):
        tmp1=dp[i-1][val]#とらない
        if val-v[i-1]<0:#この時、iこめの価値がおおきいので、これをとるだけで達成してしまう
            tmp2=w[i-1]#i=1の時、dp[0][val]=inf
        else:#i=1の時val-v[0]>0で無限になるので
            tmp2=dp[i-1][val-v[i-1]]+w[i-1]#
        res=min(tmp1,tmp2)
        dp[i][val]=res
#ここでW以下となるvalの最大値をたんさくする
max=0
for value in range(len(dp[N])):
    if dp[N][value]<=W:
        if value>max:
            max=value
print(max)


Fixed submission:
def knap(N,W,weight,value):
    inf=float("inf")
    dp=[[-inf for i in range(W+1)] for j in range(N+1)]
    #各nについて初期化　以下で各ｗについて0この時０とする
    for i in range(W+1):#w+1とは0~w
        dp[0][i]=0
    for i in range(N):#each n 0~N-1
        for w in range(W+1):#w 0~w
            if weight[i]<=w:#=を入れないとぎりぎりの時が困る
                dp[i+1][w]=max(dp[i][w-weight[i]]+value[i],dp[i][w])
            else:
                dp[i+1][w]=dp[i][w]
   # print(dp)
    return dp[N][W]


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)
print(knap(n,W,w,v))

Buggy python submission (verdict: Time Limit Exceeded):
N,W= map(int,input().split())  
wv = [tuple(map(int, input().split())) for i in range(0, N) ]   

def rec(n, uplimit_w):  
  ans = 0  
  if n == N:  
    return 0  

  # n番目の品物を使えない場合   
  elif wv[n][0] > uplimit_w:  
    return rec(n + 1, uplimit_w)  

  # n番目の品物が使える時  
  # -> n番目の品物は使った方がいいのか、使わない方がいいのか...?  
  else:  
    ans = max(  
      rec(n + 1, uplimit_w),  
      rec(n + 1, uplimit_w - wv[n][0]) + wv[n][1]  
    )  
    return ans  

def solve():  
  print(rec(0, W))  

def main():  
  solve()  

if __name__ == "__main__":  
  main()

Fixed submission:
def knap(N,W,weight,value):
    inf=float("inf")
    dp=[[-inf for i in range(W+1)] for j in range(N+1)]
    #各nについて初期化　以下で各ｗについて0この時０とする
    for i in range(W+1):#w+1とは0~w
        dp[0][i]=0
    for i in range(N):#each n 0~N-1
        for w in range(W+1):#w 0~w
            if weight[i]<=w:#=を入れないとぎりぎりの時が困る
                dp[i+1][w]=max(dp[i][w-weight[i]]+value[i],dp[i][w])
            else:
                dp[i+1][w]=dp[i][w]
   # print(dp)
    return dp[N][W]


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)
print(knap(n,W,w,v))

Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(40000000000)
def knap(n,w,weight,value,dp):
  #  print(n,":",w,":",len(dp),":",len(dp[n]))
    if dp[n][w]!=-1:
        return dp[n][w]
    if n==0:
        dp[n][w]=0
        return 0
    if w==0:
        dp[n][w]=0
        return 0
    if w-weight[n]<0:
        tmp2=knap(n-1,w,weight,value,dp)
        dp[n][w]=tmp2
        return tmp2
    tmp1=knap(n-1,w-weight[n],weight,value,dp)+value[n]
    tmp2=knap(n-1,w,weight,value,dp)
    if tmp1>tmp2:
        dp[n][w]=tmp1
        return tmp1
    else:
        dp[n][w]=tmp2
        return tmp2
        

n,W=map(int,input().split())
weight=[0]
value=[0]
for i in range(n):
    a,b=map(int,input().split())
    weight.append(a)
    value.append(b)
dp=[[-1]*(W+1)]*(n+1)
print(knap(n,W,weight,value,dp))



Fixed submission:
def knap(N,W,weight,value):
    inf=float("inf")
    dp=[[-inf for i in range(W+1)] for j in range(N+1)]
    #各nについて初期化　以下で各ｗについて0この時０とする
    for i in range(W+1):#w+1とは0~w
        dp[0][i]=0
    for i in range(N):#each n 0~N-1
        for w in range(W+1):#w 0~w
            if weight[i]<=w:#=を入れないとぎりぎりの時が困る
                dp[i+1][w]=max(dp[i][w-weight[i]]+value[i],dp[i][w])
            else:
                dp[i+1][w]=dp[i][w]
   # print(dp)
    return dp[N][W]


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)
print(knap(n,W,w,v))

Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(4000000000000)
def knap(n,w,weight,value,dp):
  #  print(n,":",w,":",len(dp),":",len(dp[n]))
    if dp[n][w]!=-1:
        return dp[n][w]
    if n==0:
        dp[n][w]=0
        return 0
    if w==0:
        dp[n][w]=0
        return 0
    if w-weight[n]<0:
        tmp2=knap(n-1,w,weight,value,dp)
        dp[n][w]=tmp2
        return tmp2
    tmp1=knap(n-1,w-weight[n],weight,value,dp)+value[n]
    tmp2=knap(n-1,w,weight,value,dp)
    if tmp1>tmp2:
        dp[n][w]=tmp1
        return tmp1
    else:
        dp[n][w]=tmp2
        return tmp2
        

n,W=map(int,input().split())
weight=[0]
value=[0]
for i in range(n):
    a,b=map(int,input().split())
    weight.append(a)
    value.append(b)
dp=[[-1]*(W+1)]*(n+1)
print(knap(n,W,weight,value,dp))



Fixed submission:
def knap(N,W,weight,value):
    inf=float("inf")
    dp=[[-inf for i in range(W+1)] for j in range(N+1)]
    #各nについて初期化　以下で各ｗについて0この時０とする
    for i in range(W+1):#w+1とは0~w
        dp[0][i]=0
    for i in range(N):#each n 0~N-1
        for w in range(W+1):#w 0~w
            if weight[i]<=w:#=を入れないとぎりぎりの時が困る
                dp[i+1][w]=max(dp[i][w-weight[i]]+value[i],dp[i][w])
            else:
                dp[i+1][w]=dp[i][w]
   # print(dp)
    return dp[N][W]


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)
print(knap(n,W,w,v))

Buggy python submission (verdict: Time Limit Exceeded):
def knap(N,W,weight,value):
    inf=float("inf")
    dp=[[-inf for i in range(W+1)] for j in range(N+1)]
    #各nについて初期化　以下で各ｗについて0この時０とする
    for i in range(W+1):#w+1とは0~w
        dp[0][i]=0
    for i in range(N):#each n 0~N-1
        for w in range(W+1):#w 0~w
            if weight[i]<=w:#=を入れないとぎりぎりの時が困る
                dp[i+1][w]=max(dp[i][w-weight[i]]+value[i],dp[i][w])
            else:
                dp[i+1][w]=dp[i][w]
   # print(dp)
    return dp[N][W]


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)
print(knap(n,W,w,v))

Fixed submission:
def knap(N,W,weight,value):
    inf=float("inf")
    dp=[[-inf for i in range(W+1)] for j in range(N+1)]
    #各nについて初期化　以下で各ｗについて0この時０とする
    for i in range(W+1):#w+1とは0~w
        dp[0][i]=0
    for i in range(N):#each n 0~N-1
        for w in range(W+1):#w 0~w
            if weight[i]<=w:#=を入れないとぎりぎりの時が困る
                dp[i+1][w]=max(dp[i][w-weight[i]]+value[i],dp[i][w])
            else:
                dp[i+1][w]=dp[i][w]
   # print(dp)
    return dp[N][W]


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)
print(knap(n,W,w,v))

Buggy python submission (verdict: Time Limit Exceeded):
class item(object):
    def __init__(self,name,Value,weight):
        self.name=name
        self.value=Value
        self.weight=weight
    def getweight(self):
        return self.weight
    def getname(self):
        return self.name
    def getvalue(self):
        return self.value
    def __str__(self):
        res="<"+str(self.name)+","+str(self.value)+","+str(self.weight)+">"
        return res
"""def sumV(itemlist):
    result=0
    for i in range(len(itemlist)):
        result+=itemlist[i].getvalue
    return result
def sumW(itemlist):
    result=0
    for i in range(len(itemlist)):
        result+=itemlist[i].getweight
    return result"""
def maxVal(toConsider,avail,result):
    if toConsider==[] or avail==0:
        result+=0
    elif toConsider[0].getweight()>avail:
        result+=maxVal(toConsider[1:],avail,result)
    else:
        withval=toConsider[0].getvalue()+maxVal(toConsider[1:],avail-toConsider[0].getweight(),result)
        #とるかとらないかを選ぶ
        withoutval=maxVal(toConsider[1:],avail,result)
        if withval>withoutval:
            result+=withval
        else:
            result+=withoutval
    return result
N,W=map(int,input().split())
result=0
items=[]
for i in range(N):
    w,v=map(int,input().split())
    items.append(item(str(i),v,w))
"""for i in range(len(items)):
    print(items[i])"""
print(maxVal(items,W,result))





Fixed submission:
def knap(N,W,weight,value):
    inf=float("inf")
    dp=[[-inf for i in range(W+1)] for j in range(N+1)]
    #各nについて初期化　以下で各ｗについて0この時０とする
    for i in range(W+1):#w+1とは0~w
        dp[0][i]=0
    for i in range(N):#each n 0~N-1
        for w in range(W+1):#w 0~w
            if weight[i]<=w:#=を入れないとぎりぎりの時が困る
                dp[i+1][w]=max(dp[i][w-weight[i]]+value[i],dp[i][w])
            else:
                dp[i+1][w]=dp[i][w]
   # print(dp)
    return dp[N][W]


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)
print(knap(n,W,w,v))

Buggy python submission (verdict: Time Limit Exceeded):
class item(object):
    def __init__(self,name,Value,weight):
        self.name=name
        self.value=Value
        self.weight=weight
    def getweight(self):
        return self.weight
    def getname(self):
        return self.name
    def getvalue(self):
        return self.value
    def __str__(self):
        res="<"+str(self.name)+","+str(self.value)+","+str(self.weight)+">"
        return res
def sumV(itemlist):
    result=0
    for i in range(len(itemlist)):
        result+=itemlist[i].getvalue
    return result
def sumW(itemlist):
    result=0
    for i in range(len(itemlist)):
        result+=itemlist[i].getweight
    return result
def maxVal(toConsider,avail,result):
    if toConsider==[] or avail==0:
        result+=0
    elif toConsider[0].getweight()>avail:
        result+=maxVal(toConsider[1:],avail,result)
    else:
        withval=toConsider[0].getvalue()+maxVal(toConsider[1:],avail-toConsider[0].getweight(),result)
        #とるかとらないかを選ぶ
        withoutval=maxVal(toConsider[1:],avail,result)
        if withval>withoutval:
            result+=withval
        else:
            result+=withoutval
    return result
N,W=map(int,input().split())
result=0
items=[]
for i in range(N):
    w,v=map(int,input().split())
    items.append(item(str(i),v,w))
"""for i in range(len(items)):
    print(items[i])"""
print(maxVal(items,W,result))




Fixed submission:
def knap(N,W,weight,value):
    inf=float("inf")
    dp=[[-inf for i in range(W+1)] for j in range(N+1)]
    #各nについて初期化　以下で各ｗについて0この時０とする
    for i in range(W+1):#w+1とは0~w
        dp[0][i]=0
    for i in range(N):#each n 0~N-1
        for w in range(W+1):#w 0~w
            if weight[i]<=w:#=を入れないとぎりぎりの時が困る
                dp[i+1][w]=max(dp[i][w-weight[i]]+value[i],dp[i][w])
            else:
                dp[i+1][w]=dp[i][w]
   # print(dp)
    return dp[N][W]


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)
print(knap(n,W,w,v))