import sys

import pdb

input = sys.stdin.readline



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

ws = []

vs = []

for _ in range(N):

  w, v = list(map(int, input().split()))

  ws.append(w)

  vs.append(v)



inf = 1e10



# Value[i番目までの品番][重さj以下]

Value = [[-inf for _ in range(W+1)] for __ in range(N)]



for load in range(W+1):

  if load < ws[0]:

    # 1番目の品物を入れようがなければスキップ

    Value[0][load] = 0

  else:

    Value[0][load] = vs[0]



for num in range(1, N):

  for load in range(W+1):

    if load >= ws[num]:   # 新しい品物を入れられるとき

      Value[num][load] = max(Value[num][load], Value[num-1][load], Value[num-1][load-ws[num]] + vs[num])

    else:   # 新しい品物を入れられないとき

      # 価値を変えることはできない

      Value[num][load] = Value[num-1][load]

      # Value[num][load] = max(Value[num][load], Value[num-1][load])



print((Value[N-1][W]))

import sys

import pdb

input = sys.stdin.readline



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

ws = []

vs = []

for _ in range(N):

  w, v = list(map(int, input().split()))

  ws.append(w)

  vs.append(v)



# Value[i番目までの品番][重さj以下]

Value = [[0 for _ in range(W+1)] for __ in range(N)]



for load in range(W+1):

  if load < ws[0]:

    # 1番目の品物を入れようがなければスキップ

    Value[0][load] = 0

  else:

    Value[0][load] = vs[0]



for num in range(1, N):

  for load in range(W+1):

    if load >= ws[num]:   # 新しい品物を入れられるとき

      Value[num][load] = max(Value[num][load], Value[num-1][load], Value[num-1][load-ws[num]] + vs[num])

    else:   # 新しい品物を入れられないとき

      # 価値を変えることはできない

      Value[num][load] = Value[num-1][load]

      # Value[num][load] = max(Value[num][load], Value[num-1][load])



print((Value[N-1][W]))

import sys
import pdb

input = sys.stdin.readline
N, W = list(map(int, input().split()))
ws = []
vs = []
for _ in range(N):
    w, v = list(map(int, input().split()))
    ws.append(w)
    vs.append(v)
inf = 1e10
# Value[i番目までの品番][重さj以下]
Value = [[-inf for _ in range(W + 1)] for __ in range(N)]
for load in range(W + 1):
    if load < ws[0]:
        # 1番目の品物を入れようがなければスキップ
        Value[0][load] = 0
    else:
        Value[0][load] = vs[0]
for num in range(1, N):
    for load in range(W + 1):
        if load >= ws[num]:  # 新しい品物を入れられるとき
            Value[num][load] = max(
                Value[num][load],
                Value[num - 1][load],
                Value[num - 1][load - ws[num]] + vs[num],
            )
        else:  # 新しい品物を入れられないとき
            # 価値を変えることはできない
            Value[num][load] = Value[num - 1][load]
            # Value[num][load] = max(Value[num][load], Value[num-1][load])
print((Value[N - 1][W]))

import sys
import pdb

input = sys.stdin.readline
N, W = list(map(int, input().split()))
ws = []
vs = []
for _ in range(N):
    w, v = list(map(int, input().split()))
    ws.append(w)
    vs.append(v)
# Value[i番目までの品番][重さj以下]
Value = [[0 for _ in range(W + 1)] for __ in range(N)]
for load in range(W + 1):
    if load < ws[0]:
        # 1番目の品物を入れようがなければスキップ
        Value[0][load] = 0
    else:
        Value[0][load] = vs[0]
for num in range(1, N):
    for load in range(W + 1):
        if load >= ws[num]:  # 新しい品物を入れられるとき
            Value[num][load] = max(
                Value[num][load],
                Value[num - 1][load],
                Value[num - 1][load - ws[num]] + vs[num],
            )
        else:  # 新しい品物を入れられないとき
            # 価値を変えることはできない
            Value[num][load] = Value[num - 1][load]
            # Value[num][load] = max(Value[num][load], Value[num-1][load])
print((Value[N - 1][W]))

-inf = 1e10 -Value = [[-inf for _ in range(W + 1)] for __ in range(N)] +Value = [[0 for _ in range(W + 1)] for __ in range(N)]