CodeEff/ECCO huggingface dataset:
# Original solution
def main():
    N, W = list(map(int, input().split()))
    wl = []
    vl = []
    for _ in range(N):
        w, v = list(map(int, input().split()))
        wl.append(w)
        vl.append(v)
    dp = [[0] * (W + 1) for _ in range(N + 1)]
    for i in range(N):
        for j in range(W + 1):
            if wl[i] > j:
                dp[i + 1][j] = dp[i][j]
            else:
                dp[i + 1][j] = max(dp[i][j], dp[i][j - wl[i]] + vl[i])
    print((dp[N][W]))


main()


# Optimized solution
def main():
    N, W = list(map(int, input().split()))
    WV = []
    for _ in range(N):
        w, v = list(map(int, input().split()))
        WV.append((w, v))
    dp = [[0] * (W + 1) for _ in range(N + 1)]
    for i in range(N):
        for j in range(W + 1):
            if j >= WV[i][0]:
                dp[i + 1][j] = max(
                    dp[i][j],
                    dp[i][j - WV[i][0]] + WV[i][1]
                )
            else:
                dp[i + 1][j] = dp[i][j]
    print((dp[-1][-1]))


main()
# Original solution
n, w = list(map(int, input().split()))
lis = [[0, 0]]
for i in  range(n):
    lis.append(list(map(int, input().split())))

dp = [[0 for i in range(w+1)] for i in range(n+1)]
#print(dp)
#print(lis)

for i in range(1, n+1):
    for j in range(w+1):
        if j - lis[i][0] < 0:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j],dp[i-1][j-lis[i][0]] + lis[i][1])
print((dp[n][w]))

# Optimized solution
n, W = list(map(int, input().split()))
w = [0] * n
v = [0] * n
for i in range(n):
    w[i],v[i] = list(map(int, input().split()))

dp = [[0] * (W + 1) for i in range(n)]
for i in range(n):
    for j in range(W+1):
        if j - w[i] < 0:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
#print(dp)
print((dp[n-1][W]))
# Original solution
from sys import stdin
n,W=list(map(int,input().split()))
k=[[0 for i in range(W+1)] for i in range(n+1)]
for i in range(1,n+1):
    w,v=list(map(int,stdin.readline().split()))
    for j in range(1,W+1):
        if w<=j:
            k[i][j]=max(v+k[i-1][j-w],k[i-1][j])
        else:
            k[i][j]=k[i-1][j]
print((k[n][W]))
        

# Optimized solution
from sys import stdin
n,W=list(map(int,input().split()))
k=[[0 for i in range(W+1)] for i in range(2)]
for i in range(1,n+1):
    w,v=list(map(int,stdin.readline().split()))
    for j in range(1,W+1):
        if w<=j:
            k[1][j]=max(v+k[0][j-w],k[0][j])
        else:
            k[1][j]=k[0][j]
    k[0]=[i for i in k[1]]
    k[1]=[0]*(W+1)
print((k[0][-1]))
# Original solution
from sys import stdin
n,W=list(map(int,input().split()))
k=[[0 for i in range(W+1)] for i in range(2)]
for i in range(1,n+1):
    w,v=list(map(int,stdin.readline().split()))
    for j in range(1,W+1):
        if w<=j:
            k[1][j]=max(v+k[0][j-w],k[0][j])
        else:
            k[1][j]=k[0][j]
    k[0]=[i for i in k[1]]
    k[1]=[0]*(W+1)
print((k[0][-1]))

# Optimized solution
from sys import stdin
n,W=list(map(int,input().split()))
dp=[0 for i in range(W+1)]
for i in range(n):
    w,v=list(map(int,stdin.readline().split()))
    for j in range(W-w,-1,-1):
        dp[j+w]=max(dp[j]+v,dp[j+w])
print((dp[-1]))
# Original solution
import sys
input = sys.stdin.readline



M, W = list(map(int, input().split()))                                # M: 品物の種類 W: 重量制限
single = True                                                   # True = 重複なし

price_list = [0]
weight_list = [0]
for _ in range(M):
    weight, price = list(map(int, input().split()))
    price_list.append(price)
    weight_list.append(weight)


################################################################################################################################################

dp_min = 0                                                      # 総和価値の最小値

""" dp[item <= M ][weight <= W] = 重さ上限を固定した時の"最大"価値 """
dp = [[dp_min] * (W + 1) for _ in range(M + 1)]                 # 左端と上端の境界条件で W, M を一個ずつ多めに取る

""" 重さ 0 の時の境界条件 """
for item in range(M+1):
    dp[item][0] = 0                                             # 重さ 0 を実現するのに必要な品物の個数は 0 個

""" 品物 0 個の時の境界条件 """
# for weight in range(W+1):
#     dp[0][weight] = dp_min                                    # 0 種類の品物で実現できる重量は存在しない　（dpの初期化で自動的に課せる場合が多い）


for item in range(1,M+1):                                       # 境界条件を除いた M 回のループ（※ f[item] = g.f[item-i] の漸化式なので、list index out of range となる）
    for weight in range(1, W + 1):
        if weight < weight_list[item]:                          # weight (重量価値) < weight_list[item] (品物の重量) の時は無視してよい
            dp[item][weight] = dp[item - 1][weight]
        else:
            temp = dp[item - single][weight - weight_list[item]] + price_list[item]  # single = True: 重複なし
            if temp > dp[item-1][weight]:                       # max(dp[item-1][weight], temp)
                dp[item][weight] = temp
            else:
                dp[item][weight] = dp[item-1][weight]

print((dp[M][W]))

# Optimized solution
import sys
input = sys.stdin.readline



N, W = list(map(int, input().split()))                                # N: 品物の種類 W: 重量制限

price_list = []
weight_list = []
for _ in range(N):
    weight, price = list(map(int, input().split()))
    price_list.append(price)
    weight_list.append(weight)


################################################################################################################################################

def max2(x,y):
    """ pythonの組み込み関数 max は２変数に対しては遅い！！ """
    if x>y:
        return x
    else:
        return y


dp_min = 0                                                      # 総和価値の最小値

""" dp[weight <= W] = 重さ上限を固定した時の"最大"価値 """
dp = [dp_min] * (W + 1)

for item in range(N):
    for weight in reversed(list(range(weight_list[item], W + 1))):
        dp[weight] = max2(dp[weight], dp[weight - weight_list[item]] + price_list[item])


print((dp[W]))
# Original solution
import sys
input = sys.stdin.readline



N, W = list(map(int, input().split()))                                # N: 品物の種類 W: 重量制限

price_list = []
weight_list = []
for _ in range(N):
    weight, price = list(map(int, input().split()))
    price_list.append(price)
    weight_list.append(weight)


################################################################################################################################################

def max2(x,y):
    """ pythonの組み込み関数 max は２変数に対しては遅い！！ """
    if x>y:
        return x
    else:
        return y


dp_min = 0                                                      # 総和価値の最小値

""" dp[weight <= W] = 重さ上限を固定した時の"最大"価値 """
dp = [dp_min] * (W + 1)

for item in range(N):
    for weight in reversed(list(range(weight_list[item], W + 1))):
        dp[weight] = max2(dp[weight], dp[weight - weight_list[item]] + price_list[item])


print((dp[W]))

# Optimized solution
import sys
input = sys.stdin.readline


def max2(x, y):
    """ pythonの組み込み関数 max は2変数に対しては遅い！！ """
    if x > y:
        return x
    else:
        return y


def knapsack_weight(single=True):
    """
    重さが小さい時のナップサックDP
    :param single: True = 重複なし
    """
    """ dp[weight <= W] = 重さ上限を固定した時の最大価値 """
    dp_min = 0  # 総和価値の最小値
    dp = [dp_min] * (W + 1)

    for item in range(N):
        if single:
            S = reversed(list(range(weight_list[item], W + 1)))
        else:
            S = list(range(weight_list[item], W + 1))
        for weight in S:
            dp[weight] = max2(dp[weight], dp[weight - weight_list[item]] + price_list[item])
    return dp[W]

#######################################################################################################


N, W = list(map(int, input().split()))                                # N: 品物の種類 W: 重量制限

price_list = []
weight_list = []
for _ in range(N):
    weight, price = list(map(int, input().split()))
    price_list.append(price)
    weight_list.append(weight)

print((knapsack_weight(single=True)))

################################################################################################################################################
# Original solution
import sys
input = sys.stdin.readline


def max2(x, y):
    """ pythonの組み込み関数 max は2変数に対しては遅い！！ """
    if x > y:
        return x
    else:
        return y


def knapsack_weight(single=True):
    """
    重さが小さい時のナップサックDP
    :param single: True = 重複なし
    """
    """ dp[weight <= W] = 重さ上限を固定した時の最大価値 """
    dp_min = 0  # 総和価値の最小値
    dp = [dp_min] * (W + 1)

    for item in range(N):
        if single:
            S = reversed(list(range(weight_list[item], W + 1)))
        else:
            S = list(range(weight_list[item], W + 1))
        for weight in S:
            dp[weight] = max2(dp[weight], dp[weight - weight_list[item]] + price_list[item])
    return dp[W]

#######################################################################################################


N, W = list(map(int, input().split()))                                # N: 品物の種類 W: 重量制限

price_list = []
weight_list = []
for _ in range(N):
    weight, price = list(map(int, input().split()))
    price_list.append(price)
    weight_list.append(weight)

print((knapsack_weight(single=True)))

################################################################################################################################################



# Optimized solution
import sys
input = sys.stdin.readline


def max2(x, y):
    """ pythonの組み込み関数 max は2変数に対しては遅い！！ """
    if x > y:
        return x
    else:
        return y


def knapsack_weight(single=True):
    """
    重さが小さい時のナップサックDP
    :param single: True = 重複なし
    """
    N, W = list(map(int, input().split()))  # N: 品物の種類 W: 重量制限

    """ dp[weight <= W] = 重さ上限を固定した時の最大価値 """
    dp_min = 0  # 総和価値の最小値
    dp = [dp_min] * (W + 1)

    for _ in range(N):
        w, price = list(map(int, input().split()))
        if single:
            S = reversed(list(range(w, W + 1)))
        else:
            S = list(range(w, W + 1))
        for weight in S:
            dp[weight] = max2(dp[weight], dp[weight - w] + price)
    return dp[W]

#######################################################################################################


print((knapsack_weight(single=True)))
# Original solution
def knapsack_weight(single=True):
    """
    重さが小さい時のナップサックDP
    :param single: True = 重複なし
    """
    """ dp[weight <= W] = 重さ上限を固定した時の最大価値 """
    dp_min = 0  # 総和価値の最小値
    dp = [dp_min] * (W + 1)

    for item in range(N):
        if single:
            S = list(range(W, weight_list[item] - 1, -1))
        else:
            S = list(range(weight_list[item], W + 1))
        for weight in S:
            if dp[weight] < dp[weight - weight_list[item]] + price_list[item]:
                dp[weight] = dp[weight - weight_list[item]] + price_list[item]
    return dp[W]

N, W = list(map(int, input().split()))                                # N: 品物の種類 W: 重量制限
 
price_list = []
weight_list = []
for _ in range(N):
    weight, price = list(map(int, input().split()))
    price_list.append(price)
    weight_list.append(weight)
 
print((knapsack_weight(single=True)))

# Optimized solution
def knapsack_weight(single=True):
    """
    重さが小さい時のナップサックDP
    :param single: True = 重複なし
    """
    """ dp[weight <= W] = 重さ上限を固定した時の最大価値 """
    dp_min = 0  # 総和価値の最小値
    dp = [dp_min] * (W + 1)

    for item in range(N):
        S = list(range(W, weight_list[item] - 1, -1))
        for weight in S:
            if dp[weight] < dp[weight - weight_list[item]] + price_list[item]:
                dp[weight] = dp[weight - weight_list[item]] + price_list[item]
    return dp[W]

import sys
input = sys.stdin.readline  

N, W = list(map(int, input().split()))                                # N: 品物の種類 W: 重量制限
 
price_list = []
weight_list = []
for _ in range(N):
    weight, price = list(map(int, input().split()))
    price_list.append(price)
    weight_list.append(weight)
 
print((knapsack_weight(single=True)))
# Original solution
inf = 2**60
'''
def table(size, init): #配列生成
  x = len(size)
  l = [init for i in range(size[x-1])]
  for i in range(x-1):
    l = [l for k in range(size[x-2-i])]
  return l
'''

n, W = list(map(int, input().split()))
w, v = [[0]*n for i in range(2)]
for i in range(n):
  w[i], v[i] = list(map(int, input().split()))

dp = [[-1] * (W+1) for i in range(n+1)]
dp[0][0] = 0

for i in range(n):
  for j in range(W+1):
    if dp[i][j] != -1:
      dp[i+1][j] = max(dp[i][j], dp[i+1][j])
      if j+w[i] <= W:
        dp[i+1][j+w[i]] = max(dp[i][j] + v[i], dp[i+1][j+w[i]])

print((max(dp[n])))

# Optimized solution
inf = 2**60
'''
def table(size, init): #配列生成
  x = len(size)
  l = [init for i in range(size[x-1])]
  for i in range(x-1):
    l = [l for k in range(size[x-2-i])]
  return l
'''

n, W = list(map(int, input().split()))
w, v = [[0]*n for i in range(2)]
for i in range(n):
  w[i], v[i] = list(map(int, input().split()))

dp = [[0] * (W+1) for i in range(n+1)]


for i in range(n):
  for j in range(W+1):
        if j>=w[i]:
            dp[i+1][j] = max(dp[i][j], dp[i][j-w[i]]+v[i])
        else:
            dp[i+1][j] = dp[i][j]

print((max(dp[n])))
# Original solution
(N, W), *D = [list(map(int, o.split())) for o in open(0)]
w, v = 0, 1
dp = [[0]*-~W for _ in [0]*-~N]
for i in range(N):
  for j in range(W + 1):
    dp[i + 1][j] = max(dp[i][j], (dp[i][j - D[i][w]] + D[i][v])*(j >= D[i][w]))
print((dp[N][W]))

# Optimized solution
N, W = list(map(int,input().split()))
dp = [0]*-~W
for _ in [None]*N:
  w, v = list(map(int,input().split()))
  for j in range(W, w-1, -1):
    dp[j] = max(dp[j], dp[j - w] + v)
print((max(dp)))
# Original solution
import sys
import math
from collections import deque
import copy

N, W = list(map(int, input().split()))
wv = [list(map(int, input().split())) for _ in range(N)]

dp = [[-1 for _ in range(W + 1)] for _ in range(N + 1)]
for i in dp:
    i[0] = 0
dp[0] = [0 for _ in range(W + 1)]

for i in range(1, N + 1):
    for l in range(1, W + 1):
        if l - wv[i - 1][0] < 0:
            dp[i][l] = dp[i - 1][l]
        else:
            dp[i][l] = max(dp[i - 1][l], dp[i - 1][l - wv[i - 1][0]] + wv[i - 1][1])
print((dp[N][W]))


# Optimized solution
N, W = list(map(int, input().split()))
wv = [list(map(int, input().split())) for _ in range(N)]

dp = [[-1 for _ in range(W + 1)] for _ in range(N + 1)]
for i in dp:
    i[0] = 0
dp[0] = [0 for _ in range(W + 1)]

for i in range(1, N + 1):
    for l in range(1, W + 1):
        if l - wv[i - 1][0] < 0:
            dp[i][l] = dp[i - 1][l]
        else:
            dp[i][l] = max(dp[i - 1][l], dp[i - 1][l - wv[i - 1][0]] + wv[i - 1][1])
print((dp[N][W]))
# Original solution
n, we = list(map(int, input().split()))

cf=[(0, 0)]*(n+1)

for i in range(1, n+1):
    cf[i] = tuple( map(int, input().split()) )

dp=[0]*(we+1)

best=0

for i in range(1, n+1):
    for j in reversed(list(range(cf[i][0], we+1))):
        dp[j]=max( dp[j], dp[j-cf[i][0]]+ cf[i][1] )
        
    best=max(best, dp[we])


print(best)

# for i in range(1, n+1): print( dp[i], '\n' )

# Optimized solution
import sys

n, we = list(map(int, input().split()))

cf=[(0, 0)]*(n+1)

for i in range(1, n+1):
    cf[i] = tuple( map(int, sys.stdin.readline().split()) )

dp=[0]*(we+1)

best=0

for i in range(1, n+1):
    for j in reversed(list(range(cf[i][0], we+1))):
        dp[j]=max( dp[j], dp[j-cf[i][0]]+ cf[i][1] )
        
    best=max(best, dp[we])


print(best)

# for i in range(1, n+1): print( dp[i], '\n' )
# Original solution
import sys

n, we = list(map(int, input().split()))

cf=[(0, 0)]*n

cf = sorted(tuple( int(x) for x in sys.stdin.readline().split()) for _ in range(n))

dp=[0]*(we+1)

best=0

for w,c in cf:
    for j in reversed(list(range(w, we+1))):
        if dp[j]<dp[j-w]+ c : dp[j]=dp[j-w]+ c
    # print(dp)
    best=max(best, dp[we])


print(best)

# Optimized solution
n, we = list(map(int, input().split()))

cf=[(0, 0)]*n

cf = sorted(tuple( int(x) for x in input().split()) for _ in range(n))

dp=[0]*(we+1)

best=0
cnt=1
lim=0

for w,c in cf:
    cnt=cnt+w
    lim=min(cnt, we-w)
    for j in range(lim, -1, -1):
        if dp[j+w]<(dp[j] + c) : dp[j+w]=dp[j] + c

print((max(dp)))
# Original solution
import sys

n, we = list(map(int, input().split()))

cf=[(0, 0)]*n

cf = sorted(tuple( int(x) for x in sys.stdin.readline().split()) for _ in range(n))

dp=[0]*(we+1)

best=0
cnt=1
lim=0

for w,c in cf:
    cnt=cnt+w
    lim=min(cnt, we-w)
    for j in range(lim, -1, -1):
        if dp[j+w]<(dp[j] + c) : dp[j+w]=dp[j] + c

print((max(dp)))

# Optimized solution
import sys

n, we = list(map(int, input().split()))

cf=[(0, 0)]*n

cf = sorted( [[int(x) for x in sys.stdin.readline().split()] for _ in range(n)] )

dp=[0]*(we+1)

best=0
cnt=1
lim=0

for w,c in cf:
    cnt=cnt+w
    lim=min(cnt, we-w)
    for j in range(lim, -1, -1):
        if dp[j+w]<(dp[j] + c) : dp[j+w]=dp[j] + c

print((max(dp)))
# Original solution
import sys
n, W = list(map(int, sys.stdin.readline().split()))
#L = [[map(int, sys.stdin.readline().split())] for _ in range(n)]
dp = [[0 for _ in range(W+1)] for _ in range(n)]
for i in range(n):
    w, v =list(map(int, sys.stdin.readline().split()))
    for j in range(W+1):
        dp[i][j] = max(dp[i-1][j], dp[i][j])
        if dp[i-1][j] !=0 and j+w<=W:
            dp[i][j+w] = max(dp[i-1][j+w], v+ dp[i-1][j])
            #print(dp, i)
        
    dp[i][w] = max(dp[i-1][w], v)
    

#print(dp)  
print((max(dp[-1])))

# Optimized solution
import sys
n, W = list(map(int, sys.stdin.readline().split()))
dp = [[0 for _ in range(W+1)] for _ in range(n)]
for i in range(n):
    w, v =list(map(int, sys.stdin.readline().split()))
    for j in range(W+1):
        dp[i][j] = max(dp[i-1][j], dp[i][j])
        if dp[i-1][j] !=0 and j+w<=W:
            dp[i][j+w] = max(dp[i-1][j+w], v+ dp[i-1][j])
            #print(dp, i)
        
    dp[i][w] = max(dp[i-1][w], v)
    
#print(dp)  
print((max(dp[-1])))
# Original solution
N, W = list(map(int, input().split()))
wv = [[0 for i in range(2)] for j in range(N)]
dp = [[0 for i in range(N+1)] for j in range(W+1)]

for i in range(N):
  wv[i] = list(map(int, input().split()))

for i in range(N):
  for w in range(1,W+1):
    if w < wv[i][0]:
      dp[w][i+1] = dp[w][i]
    else:
      dp[w][i+1] = max(dp[w-wv[i][0]][i]+wv[i][1], dp[w][i])

print((dp[-1][-1]))


# Optimized solution
N,W=list(map(int,input().split()))
wv = [tuple(map(int,input().split())) for _ in range(N)]

dp = [[0]*(W+1) for _ in range(N+1)]

for i in range(1,N+1):
  for j in range(1, W+1):
    if j >= wv[i-1][0]:
      dp[i][j] = max(dp[i-1][j], dp[i-1][j-wv[i-1][0]]+wv[i-1][1])
    else:
      dp[i][j] = dp[i-1][j]
      
print((dp[-1][-1]))
# Original solution
import sys
#import numpy as np
#from collections import defaultdict
import math
#from collections import deque

input = sys.stdin.readline
#import numpy as np



def main():

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

    dp = [0] * (W+2)

    for _ in range(N):
        w,v = list(map(int,input().split()))

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

    print((dp[W]))
#    print(dp)




if __name__ == "__main__":
    main()

# Optimized solution
import sys
input = sys.stdin.readline
#import numpy as np



def main():

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

    dp = [0] * (W+2)

    for _ in range(N):
        w,v = list(map(int,input().split()))

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

    print((dp[W]))



if __name__ == "__main__":
    main()
# Original solution
import sys


def input():
    return sys.stdin.readline().rstrip()


def main():
    N, W = list(map(int, input().split()))
    dp = [[0] * (N + 1) for _ in range(W + 1)]
    for i in range(1, N + 1):
        w, v = list(map(int, input().split()))
        for j in range(W + 1):
            if j >= w:
                dp[j][i] = max(dp[j][i - 1], dp[j - w][i-1] + v)
            else:
                dp[j][i] = dp[j][i - 1]

    print((dp[W][N]))


if __name__ == "__main__":
    main()


# Optimized solution
import sys
import math
import itertools


# \n


def input():
    return sys.stdin.readline().rstrip()


def main():
    N, WW = list(map(int, input().split()))
    W = []
    V = []
    for i in range(N):
        w, v = list(map(int, input().split()))
        W.append(w)
        V.append(v)

    dp = [[0] * (WW+1) for _ in range(N)]

    for i in range(N):
        w = W[i]
        v = V[i]
        for j in range(WW+1):
            if w<=j:
                dp[i][j] =max(dp[i-1][j],dp[i-1][j-w]+v)
            else:
                dp[i][j] =dp[i-1][j]

    print((max(dp[N-1])))


if __name__ == "__main__":
    main()
# Original solution
import sys
import math
import itertools


# \n


def input():
    return sys.stdin.readline().rstrip()


def main():
    N, WW = list(map(int, input().split()))

    dp = [[0] * (WW+1) for _ in range(N)]

    for i in range(N):
        w, v = list(map(int, input().split()))
        for j in range(WW+1):
            if w<=j:
                dp[i][j] =max(dp[i-1][j],dp[i-1][j-w]+v)
            else:
                dp[i][j] =dp[i-1][j]

    print((max(dp[N-1])))


if __name__ == "__main__":
    main()


# Optimized solution
import sys


# \n
def input():
    return sys.stdin.readline().rstrip()


def main():
    N, W = list(map(int, input().split()))
    dp =[0] *(W+1)
    for i in range(N):
        w,v =list(map(int,input().split()))

        for i in range(W,w-1,-1):
            dp[i] =max(dp[i],dp[i-w]+v)



    print((max(dp)))





if __name__ == "__main__":
    main()
# Original solution
import sys
input = sys.stdin.readline
N, W = list(map(int, input().split()))
 
dpt = [0] * (W+1)
 
for i in range(N):
    w, v = list(map(int, input().split()))
    for j in range(W, w-1, -1):
        a = dpt[j]
        b = dpt[j-w]+v
        if a > b:
            dpt[j] = a
        else:
            dpt[j] = b
 
print((dpt[W]))

# Optimized solution
import sys
input = sys.stdin.readline
def main():
    N, W = list(map(int, input().split()))
    
    dpt = [0] * (W+1)
    
    for i in range(N):
        w, v = list(map(int, input().split()))
        for j in range(W, w-1, -1):
            a = dpt[j]
            b = dpt[j-w]+v
            if a > b:
                dpt[j] = a
            else:
                dpt[j] = b
    
    print((dpt[W]))

if __name__ == '__main__':
    main()
# Original solution
# atcoder https://atcoder.jp/contests/dp/tasks/dp_d
def main():
    N, W = list(map(int, input().split()))
    w, v = [], []
    for _ in range(N):
        wi, vi = list(map(int, input().split()))
        w.append(wi)
        v.append(vi)


    dp = [[0 for j in range(W+1)] for i in range(N+1)]

    for i in range(1, N+1):
        for j in range(1, W+1):
            if j >= w[i-1]:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]]+v[i-1])
            else:
                dp[i][j] = dp[i-1][j]

    print((dp[N][W]))

main()

# Optimized solution
# https://atcoder.jp/contests/dp/tasks/dp_d

def INT(): return int(eval(input()))
def MAP(): return list(map(int, input().split()))
def LIST(): return list(map(int, input().split()))

N, W = MAP()
w, v = [], []
for _ in range(N):
    wi, vi = MAP()
    w.append(wi)
    v.append(vi)

DP = [[0] * (N+1) for _ in range(W+1)]

for i in range(1, W+1):
    for j in range(1, N+1):
        if i < w[j-1]:
            DP[i][j] = max(
                DP[i][j-1],
                DP[i-1][j])
        else:
            DP[i][j] = max(
                DP[i][j-1],
                DP[i-w[j-1]][j-1] + v[j-1],
                DP[i-1][j])

print((DP[-1][-1]))
# Original solution
N, W = list(map(int, input().split()))
dp = [[0 for i in range(W + 1)] for j in range(N+1)]

for j in range(N):
    w, v = list(map(int, input().split()))
    for k in range(W + 1):
        if k >= w:
            dp[j+1][k] = max(dp[j][k-w] + v, dp[j][k])
        else:
            dp[j+1][k] = dp[j][k]
ans = 0
for i in range(W + 1):
    ans = max(ans, dp[N][i])
print((dp[N][W]))


# Optimized solution
N, W = list(map(int, input().split()))
dp = [[0 for i in range(W + 1)] for j in range(N+1)]

for j in range(N):
    w, v = list(map(int, input().split()))
    for k in range(W + 1):
        if k >= w:
            dp[j+1][k] = max(dp[j][k-w] + v, dp[j][k])
        else:
            dp[j+1][k] = dp[j][k]

print((dp[N][W]))