Buggy python submission (verdict: Time Limit Exceeded):
n,W=list(map(int,input().split()))
li=[]
wr=[0]*n
vr=[0]*n
dd = [[0 for _ in range(W+1)] for k in range(n+1)]

for i in range(n):
	w,v=map(int,input().split())
	wr[i]=w
	vr[i]=v
mw=min(wr)
def maxv(i,w):
	if dd[i][w]!=0:
		
		return dd[i][w]
	if i==n:
		return 0
	if W-w<mw:
		return 0
	if w+wr[i]<=W:
		a=vr[i]+maxv(i+1,w+wr[i])
	else:
		a=0
	b=maxv(i+1,w)
	c=max(a,b)
	dd[i][w]=c
	return c
print(maxv(0,0))



Fixed submission:
n,W=map(int,input().split())
dp=[0]*(W+1)
dd=dp.copy()
for i in range(n):
	w,v=map(int,input().split())
	for j in range(W):
		cw=j+w
		cv=dp[j]+v
		if cw <=W and dd[cw]<cv:
			dd[cw]=cv
	dp=dd.copy()
print(dp[W])

Buggy python submission (verdict: Runtime Error):
import numba as nb 
from collections import defaultdict
n,W=list(map(int,input().split()))
li=[]
wr=[0]*n
vr=[0]*n
dd=defaultdict(lambda:0)
for i in range(n):
	w,v=map(int,input().split())
	wr[i]=w
	vr[i]=v
mw=min(wr)


@nb.njit()
def maxv(i,w):
	if dd[(i,w)]!=0:
		
		return dd[(i,w)]
	if i==n:
		return 0
	if W-w<mw:
		return 0
	if w+wr[i]<=W:
		a=vr[i]+maxv(i+1,w+wr[i])
	else:
		a=0
	b=maxv(i+1,w)
	c=max(a,b)
	dd[(i,w)]=c
	return c
print(maxv(0,0))



Fixed submission:
n,W=map(int,input().split())
dp=[0]*(W+1)
dd=dp.copy()
for i in range(n):
	w,v=map(int,input().split())
	for j in range(W):
		cw=j+w
		cv=dp[j]+v
		if cw <=W and dd[cw]<cv:
			dd[cw]=cv
	dp=dd.copy()
print(dp[W])

Buggy python submission (verdict: Runtime Error):
from collections import defaultdict
n,W=list(map(int,input().split()))
li=[]
wr=[0]*n
vr=[0]*n
dd=defaultdict(lambda:0)
for i in range(n):
	w,v=map(int,input().split())
	wr[i]=w
	vr[i]=v
mw=min(wr)
import numba as nb 

@nb.njit()
def maxv(i,w):
	if dd[(i,w)]!=0:
		
		return dd[(i,w)]
	if i==n:
		return 0
	if W-w<mw:
		return 0
	if w+wr[i]<=W:
		a=vr[i]+maxv(i+1,w+wr[i])
	else:
		a=0
	b=maxv(i+1,w)
	c=max(a,b)
	dd[(i,w)]=c
	return c
print(maxv(0,0))



Fixed submission:
n,W=map(int,input().split())
dp=[0]*(W+1)
dd=dp.copy()
for i in range(n):
	w,v=map(int,input().split())
	for j in range(W):
		cw=j+w
		cv=dp[j]+v
		if cw <=W and dd[cw]<cv:
			dd[cw]=cv
	dp=dd.copy()
print(dp[W])

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
n,W=list(map(int,input().split()))
li=[]
wr=[0]*n
vr=[0]*n
dd=defaultdict(lambda:0)
for i in range(n):
	w,v=map(int,input().split())
	wr[i]=w
	vr[i]=v
mw=min(wr)
def maxv(i,w):
	if dd[(i,w)]!=0:
		
		return dd[(i,w)]
	if i==n:
		return 0
	if W-w<mw:
		return 0
	if w+wr[i]<=W:
		a=vr[i]+maxv(i+1,w+wr[i])
	else:
		a=0
	b=maxv(i+1,w)
	c=max(a,b)
	dd[(i,w)]=c
	return c
print(maxv(0,0))



Fixed submission:
n,W=map(int,input().split())
dp=[0]*(W+1)
dd=dp.copy()
for i in range(n):
	w,v=map(int,input().split())
	for j in range(W):
		cw=j+w
		cv=dp[j]+v
		if cw <=W and dd[cw]<cv:
			dd[cw]=cv
	dp=dd.copy()
print(dp[W])

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
n,W=list(map(int,input().split()))
li=[]
wr=[0]*n
vr=[0]*n
dd=defaultdict(lambda:0)
for i in range(n):
	w,v=map(int,input().split())
	wr[i]=w
	vr[i]=v
mw=min(wr)
def maxv(i,w):
	if dd[(i,w)]!=0:
		return dd[(i,w)]
	if i==n:
		return 0
	if W-w<mw:
		return 0
	if w+wr[i]>W:
		m=maxv(i+1,w)
		dd[(i,w)]=m
		return m
	a=vr[i]+maxv(i+1,w+wr[i])
	b=maxv(i+1,w)
	c=max(a,b)
	dd[(i,w)]=c
	return c
print(maxv(0,0))



Fixed submission:
n,W=map(int,input().split())
dp=[0]*(W+1)
dd=dp.copy()
for i in range(n):
	w,v=map(int,input().split())
	for j in range(W):
		cw=j+w
		cv=dp[j]+v
		if cw <=W and dd[cw]<cv:
			dd[cw]=cv
	dp=dd.copy()
print(dp[W])

Buggy python submission (verdict: Time Limit Exceeded):
#from collections import defaultdict
n,W=list(map(int,input().split()))
li=[]
wr=[0]*n
vr=[0]*n
#dd=defaultdict(lambda:0)
for i in range(n):
	w,v=map(int,input().split())
	wr[i]=w
	vr[i]=v
def maxv(i,w):
	#if dd[(i,w)]!=0:
#		return dd[(i,w)]
	if i==n:
		return 0
	if w+wr[i]>W:
		m=maxv(i+1,w)
		#dd[(i,w)]=m
		return m
	a=vr[i]+maxv(i+1,w+wr[i])
	b=maxv(i+1,w)
	c=max(a,b)
	return c
print(maxv(0,0))



Fixed submission:
n,W=map(int,input().split())
dp=[0]*(W+1)
dd=dp.copy()
for i in range(n):
	w,v=map(int,input().split())
	for j in range(W):
		cw=j+w
		cv=dp[j]+v
		if cw <=W and dd[cw]<cv:
			dd[cw]=cv
	dp=dd.copy()
print(dp[W])

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
n,W=list(map(int,input().split()))
li=[]
wr=[0]*n
vr=[0]*n
dd=defaultdict(lambda:0)
for i in range(n):
	w,v=map(int,input().split())
	wr[i]=w
	vr[i]=v
def maxv(i,w):
	if dd[(i,w)]!=0:
		return dd[(i,w)]
	if i==n:
		return 0
	if w+wr[i]>W:
		m=maxv(i+1,w)
		dd[(i,w)]=m
		return m
	a=vr[i]+maxv(i+1,w+wr[i])
	b=maxv(i+1,w)
	c=max(a,b)
	dd[(i,w)]=c
	return c
print(maxv(0,0))



Fixed submission:
n,W=map(int,input().split())
dp=[0]*(W+1)
dd=dp.copy()
for i in range(n):
	w,v=map(int,input().split())
	for j in range(W):
		cw=j+w
		cv=dp[j]+v
		if cw <=W and dd[cw]<cv:
			dd[cw]=cv
	dp=dd.copy()
print(dp[W])

Buggy python submission (verdict: Runtime Error):
from collections import defaultdict
n,W=list(map(int,input().split()))
li=[]
wr=[0]*n
vr=[0]*n
dd=defaultdict(lambda:0)
for i in range(n):
	w,v=map(int,input().split())
	wr[i]=w
	vr[i]=v
def maxv(i,w):
	if dd[(i,w)]!=0:
		return dd[(i,w)]
	if i==n:
		return 0
	if w+wr[i]>W:
		m=maxv(i+1,w)
		dp[(i,w)]=m
		return m
	a=vr[i]+maxv(i+1,w+wr[i])
	b=maxv(i+1,w)
	c=max(a,b)
	dd[(i,w)]=c
	return c
print(maxv(0,0))



Fixed submission:
n,W=map(int,input().split())
dp=[0]*(W+1)
dd=dp.copy()
for i in range(n):
	w,v=map(int,input().split())
	for j in range(W):
		cw=j+w
		cv=dp[j]+v
		if cw <=W and dd[cw]<cv:
			dd[cw]=cv
	dp=dd.copy()
print(dp[W])

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
n,W=list(map(int,input().split()))
li=[]
wr=[0]*n
vr=[0]*n
dd=defaultdict(lambda:0)
for i in range(n):
	w,v=map(int,input().split())
	wr[i]=w
	vr[i]=v
def maxv(i,w):
	if dd[(i,w)]!=0:
		return dd[(i,w)]
	if i==n:
		return 0
	if w+wr[i]>W:
		return maxv(i+1,w)
	a=vr[i]+maxv(i+1,w+wr[i])
	b=maxv(i+1,w)
	c=max(a,b)
	dd[(i,w)]=c
	return c
print(maxv(0,0))



Fixed submission:
n,W=map(int,input().split())
dp=[0]*(W+1)
dd=dp.copy()
for i in range(n):
	w,v=map(int,input().split())
	for j in range(W):
		cw=j+w
		cv=dp[j]+v
		if cw <=W and dd[cw]<cv:
			dd[cw]=cv
	dp=dd.copy()
print(dp[W])