Buggy python submission (verdict: Time Limit Exceeded):
def knapsack(n,w):
    global weight,value,bag
    if(n==0 or w==0):
        return 0
    if(bag[n][w]!=-1):
        return bag[n][w]
    if(weight[n-1]<=w):
        bag[n][w]=max(value[n-1] + knapsack(n-1,w-weight[n-1]),knapsack(n-1,w))
        return bag[n][w]
    else:
        bag[n][w]=knapsack(n-1,w)
        return bag[n][w]
n,w=map(int,input().split())
weight=[]
value=[]
bag=[[-1 for j in range(w+1)] for i in range(n+1)]
for _ in range(n):
    tempw,tempv=map(int,input().split())
    weight.append(tempw)
    value.append(tempv)
temp=knapsack(n,w)
print(temp)

Fixed submission:
import array
n,w=map(int,input().split())
weight=[]
value=[]
for _ in range(n):
    tempw,tempv=map(int,input().split())
    weight.append(tempw)
    value.append(tempv)
t=[[0 for i in range(n+1)] for j in range(w+1)]
for i in range(1,w+1):
    for j in range(1,n+1):
        if(weight[j-1]<=i):
            t[i][j]=max(value[j-1]+t[i-weight[j-1]][j-1],t[i][j-1])
        else:
            t[i][j]=t[i][j-1]
print(t[-1][-1])

Buggy python submission (verdict: Time Limit Exceeded):
def knapsack(n,w):
    global weight,value,bag
    if(n==0 or w==0):
        return 0
    temp=str(n)+' '+str(w)
    if(temp in bag):
        return bag[temp]
    if(weight[n-1]<=w):
        bag[temp]=max(value[n-1] + knapsack(n-1,w-weight[n-1]),knapsack(n-1,w))
        return bag[temp]
    else:
        bag[temp]=knapsack(n-1,w)
        return bag[temp]
n,w=map(int,input().split())
weight=[]
value=[]
bag=dict()
for _ in range(n):
    tempw,tempv=map(int,input().split())
    weight.append(tempw)
    value.append(tempv)
temp=knapsack(n,w)
print(temp)

Fixed submission:
import array
n,w=map(int,input().split())
weight=[]
value=[]
for _ in range(n):
    tempw,tempv=map(int,input().split())
    weight.append(tempw)
    value.append(tempv)
t=[[0 for i in range(n+1)] for j in range(w+1)]
for i in range(1,w+1):
    for j in range(1,n+1):
        if(weight[j-1]<=i):
            t[i][j]=max(value[j-1]+t[i-weight[j-1]][j-1],t[i][j-1])
        else:
            t[i][j]=t[i][j-1]
print(t[-1][-1])

Buggy python submission (verdict: Time Limit Exceeded):
n,w=map(int,input().split())
weight=[]
value=[]
for _ in range(n):
    tempw,tempv=map(int,input().split())
    weight.append(tempw)
    value.append(tempv)
t=[[0 for i in range(n+1)] for j in range(w+1)]
for i in range(1,w+1):
    for j in range(1,n+1):
        if(weight[j-1]<=i):
            t[i][j]=max(value[j-1]+t[i-weight[j-1]][j-1],t[i][j-1])
        else:
            t[i][j]=t[i][j-1]
print(t[-1][-1])


Fixed submission:
import array
n,w=map(int,input().split())
weight=[]
value=[]
for _ in range(n):
    tempw,tempv=map(int,input().split())
    weight.append(tempw)
    value.append(tempv)
t=[[0 for i in range(n+1)] for j in range(w+1)]
for i in range(1,w+1):
    for j in range(1,n+1):
        if(weight[j-1]<=i):
            t[i][j]=max(value[j-1]+t[i-weight[j-1]][j-1],t[i][j-1])
        else:
            t[i][j]=t[i][j-1]
print(t[-1][-1])

Buggy python submission (verdict: Time Limit Exceeded):
def knapsack(n,w):
    global weight,value,bag
    if(n==0 or w==0):
        return 0
    if(bag[n][w]!=-1):
        return bag[n][w]
    if(weight[n-1]<=w):
        bag[n][w]=max(value[n-1] + knapsack(n-1,w-weight[n-1]),knapsack(n-1,w))
        return bag[n][w]
    else:
        bag[n][w]=knapsack(n-1,w)
        return bag[n][w]
n,w=map(int,input().split())
weight=[]
value=[]
bag=[[-1 for j in range(w+1)] for i in range(n+1)]
for _ in range(n):
    tempw,tempv=map(int,input().split())
    weight.append(tempw)
    value.append(tempv)
temp=knapsack(n,w)
print(temp)


Fixed submission:
import array
n,w=map(int,input().split())
weight=[]
value=[]
for _ in range(n):
    tempw,tempv=map(int,input().split())
    weight.append(tempw)
    value.append(tempv)
t=[[0 for i in range(n+1)] for j in range(w+1)]
for i in range(1,w+1):
    for j in range(1,n+1):
        if(weight[j-1]<=i):
            t[i][j]=max(value[j-1]+t[i-weight[j-1]][j-1],t[i][j-1])
        else:
            t[i][j]=t[i][j-1]
print(t[-1][-1])

Buggy python submission (verdict: Time Limit Exceeded):
def knapsack(n,w):
    global weight,value,bag
    if(n==0 or w==0):
        return 0
    temp=str(n)+' '+str(w)
    if(temp in bag):
        return bag[temp]
    if(weight[n-1]<=w):
        bag[temp]=max(value[n-1] + knapsack(n-1,w-weight[n-1]),knapsack(n-1,w))
        return bag[temp]
    else:
        bag[temp]=knapsack(n-1,w)
        return bag[temp]
n,w=map(int,input().split())
weight=[]
value=[]
bag=dict()
for _ in range(n):
    tempw,tempv=map(int,input().split())
    weight.append(tempw)
    value.append(tempv)
temp=knapsack(n,w)
print(temp)


Fixed submission:
import array
n,w=map(int,input().split())
weight=[]
value=[]
for _ in range(n):
    tempw,tempv=map(int,input().split())
    weight.append(tempw)
    value.append(tempv)
t=[[0 for i in range(n+1)] for j in range(w+1)]
for i in range(1,w+1):
    for j in range(1,n+1):
        if(weight[j-1]<=i):
            t[i][j]=max(value[j-1]+t[i-weight[j-1]][j-1],t[i][j-1])
        else:
            t[i][j]=t[i][j-1]
print(t[-1][-1])