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])))
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])))
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])))

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])))

-dp = [[-1] * (W + 1) for i in range(n + 1)] -dp[0][0] = 0 +dp = [[0] * (W + 1) for i in range(n + 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]]) +        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]