Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
"""
Created on Tue Jan 21 18:19:39 2020

@author: matsui
"""


N,W=map(int,input().split())
dp=[0]*(W+1)
L = sorted([list(map(int,input().split())) for i in range(N)])
s=0

for w, v in L:
    s+=w
    for j in range(min(W,s),w-1,-1):
        dp[j]=max(dp[j],dp[j-w]+v) 
    
print(max(dp))


Fixed submission:
# -*- coding: utf-8 -*-
"""
Created on Tue Jan 21 18:19:39 2020

@author: matsui
"""


N,W=map(int,input().split())
dp=[0]*(W+1)
L = sorted([list(map(int,input().split())) for i in range(N)])
s=0

for w, v in L:
    s+=w
    for j in range(min(W,s),w-1,-1):
        if dp[j-w]+v > dp[j]: dp[j]=dp[j-w]+v
    
print(max(dp))

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
"""
Created on Tue Jan 21 18:19:39 2020

@author: matsui
"""

def napsak(N,K):
    dp=[0]*(W+1)
    for i in range(1,N+1):
        #print(dp)
        w,v=map(int,input().split())
        
        for j in range(W,w-1,-1):
            dp[j]=max(dp[j],dp[j-w]+v) 
        
    return dp[-1]

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


Fixed submission:
# -*- coding: utf-8 -*-
"""
Created on Tue Jan 21 18:19:39 2020

@author: matsui
"""


N,W=map(int,input().split())
dp=[0]*(W+1)
L = sorted([list(map(int,input().split())) for i in range(N)])
s=0

for w, v in L:
    s+=w
    for j in range(min(W,s),w-1,-1):
        if dp[j-w]+v > dp[j]: dp[j]=dp[j-w]+v
    
print(max(dp))

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
"""
Created on Tue Jan 21 18:19:39 2020

@author: matsui
"""

def napsak(N,K):
    dp=[0]*(W+1)
    for i in range(1,N+1):
        #print(dp)
        w,v=map(int,input().split())
        A=dp[:w]
        A.extend([max(dp[j],dp[j-w]+v) for j in range(w,W+1)])
        dp=A
    return dp[-1]

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


Fixed submission:
# -*- coding: utf-8 -*-
"""
Created on Tue Jan 21 18:19:39 2020

@author: matsui
"""


N,W=map(int,input().split())
dp=[0]*(W+1)
L = sorted([list(map(int,input().split())) for i in range(N)])
s=0

for w, v in L:
    s+=w
    for j in range(min(W,s),w-1,-1):
        if dp[j-w]+v > dp[j]: dp[j]=dp[j-w]+v
    
print(max(dp))

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
"""
Created on Tue Jan 21 18:19:39 2020

@author: matsui
"""

def napsak(N,K):
    dp=[0]*(W+1)
    for i in range(1,N+1):
        #print(dp)
        w,v=map(int,input().split())
        A=dp[:w]
        A.extend([max(dp[j],dp[j-w]+v) for j in range(w,W+1)])
        dp=A
    return max(dp)

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


Fixed submission:
# -*- coding: utf-8 -*-
"""
Created on Tue Jan 21 18:19:39 2020

@author: matsui
"""


N,W=map(int,input().split())
dp=[0]*(W+1)
L = sorted([list(map(int,input().split())) for i in range(N)])
s=0

for w, v in L:
    s+=w
    for j in range(min(W,s),w-1,-1):
        if dp[j-w]+v > dp[j]: dp[j]=dp[j-w]+v
    
print(max(dp))

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
"""
Created on Tue Jan 21 18:19:39 2020

@author: matsui
"""

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

dp=[0]*(W+1)
for i in range(1,N+1):
    #print(dp)
    w,v=map(int,input().split())
    A=dp[:w]
    A.extend([max(dp[j],dp[j-w]+v) for j in range(w,W+1)])
    dp=A
   
print(max(dp))


Fixed submission:
# -*- coding: utf-8 -*-
"""
Created on Tue Jan 21 18:19:39 2020

@author: matsui
"""


N,W=map(int,input().split())
dp=[0]*(W+1)
L = sorted([list(map(int,input().split())) for i in range(N)])
s=0

for w, v in L:
    s+=w
    for j in range(min(W,s),w-1,-1):
        if dp[j-w]+v > dp[j]: dp[j]=dp[j-w]+v
    
print(max(dp))

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
"""
Created on Tue Jan 21 18:19:39 2020

@author: matsui
"""

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

dp=dict()
dp[0]=[0]*(W+1)
for i in range(1,N+1):
    w,v=map(int,input().split())
    tmp=dp[i-1][:w]
    for j in range(w,W+1):
        tmp.append(max(dp[i-1][j],dp[i-1][j-w]+v))
    dp[i]=tmp
   
print(max(dp[N]))

Fixed submission:
# -*- coding: utf-8 -*-
"""
Created on Tue Jan 21 18:19:39 2020

@author: matsui
"""


N,W=map(int,input().split())
dp=[0]*(W+1)
L = sorted([list(map(int,input().split())) for i in range(N)])
s=0

for w, v in L:
    s+=w
    for j in range(min(W,s),w-1,-1):
        if dp[j-w]+v > dp[j]: dp[j]=dp[j-w]+v
    
print(max(dp))

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
"""
Created on Tue Jan 21 18:19:39 2020

@author: matsui
"""

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

dp=dict()
dp[0]=[0]*(W+1)
for i in range(1,N+1):
    #print(dp)
    dp[i]=[0]*(W+1)
    w,v=map(int,input().split())
    for j in range(w):
        dp[i][j]=dp[i-1][j]
    for j in range(w,W+1):
        dp[i][j]=max(dp[i-1][j],dp[i-1][j-w]+v)
   
print(max(dp[N]))

Fixed submission:
# -*- coding: utf-8 -*-
"""
Created on Tue Jan 21 18:19:39 2020

@author: matsui
"""


N,W=map(int,input().split())
dp=[0]*(W+1)
L = sorted([list(map(int,input().split())) for i in range(N)])
s=0

for w, v in L:
    s+=w
    for j in range(min(W,s),w-1,-1):
        if dp[j-w]+v > dp[j]: dp[j]=dp[j-w]+v
    
print(max(dp))