import sys

sys.setrecursionlimit(2147483647)

INF=float("inf")

MOD=10**9+7

input=lambda :sys.stdin.buffer.readline().rstrip()

def resolve():

    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 _ in range(n+1)]

    for i in range(n):

        for k in range(w+1):

            if(k+W[i]<=w):

                dp[i+1][k+W[i]]=max(dp[i][k]+V[i],dp[i+1][k+W[i]])

            dp[i+1][k]=max(dp[i+1][k],dp[i][k])

    print((dp[n][w]))

resolve()
import sys

sys.setrecursionlimit(2147483647)

INF=float("inf")

MOD=10**9+7

input=lambda :sys.stdin.readline().rstrip()

def resolve():

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

    w=[0]*(n+1)

    v=[0]*(n+1)

    for i in range(1,n+1):

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

    dp=[0]*(W+1)

    for i in range(1,n+1): # i番目を見る

        newdp=dp[:]

        for j in range(W+1):

            if(j+w[i]<=W):

                newdp[j+w[i]]=max(newdp[j+w[i]],dp[j]+v[i])

        dp=newdp

    print((dp[-1]))

resolve()
import sys

sys.setrecursionlimit(2147483647)
INF = float("inf")
MOD = 10**9 + 7
input = lambda: sys.stdin.buffer.readline().rstrip()


def resolve():
    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 _ in range(n + 1)]
    for i in range(n):
        for k in range(w + 1):
            if k + W[i] <= w:
                dp[i + 1][k + W[i]] = max(dp[i][k] + V[i], dp[i + 1][k + W[i]])
            dp[i + 1][k] = max(dp[i + 1][k], dp[i][k])
    print((dp[n][w]))


resolve()

import sys

sys.setrecursionlimit(2147483647)
INF = float("inf")
MOD = 10**9 + 7
input = lambda: sys.stdin.readline().rstrip()


def resolve():
    n, W = list(map(int, input().split()))
    w = [0] * (n + 1)
    v = [0] * (n + 1)
    for i in range(1, n + 1):
        w[i], v[i] = list(map(int, input().split()))
    dp = [0] * (W + 1)
    for i in range(1, n + 1):  # i番目を見る
        newdp = dp[:]
        for j in range(W + 1):
            if j + w[i] <= W:
                newdp[j + w[i]] = max(newdp[j + w[i]], dp[j] + v[i])
        dp = newdp
    print((dp[-1]))


resolve()

-input = lambda: sys.stdin.buffer.readline().rstrip() +input = lambda: sys.stdin.readline().rstrip() -    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 _ in range(n + 1)] -    for i in range(n): -        for k in range(w + 1): -            if k + W[i] <= w: -                dp[i + 1][k + W[i]] = max(dp[i][k] + V[i], dp[i + 1][k + W[i]]) -            dp[i + 1][k] = max(dp[i + 1][k], dp[i][k]) -    print((dp[n][w])) +    n, W = list(map(int, input().split())) +    w = [0] * (n + 1) +    v = [0] * (n + 1) +    for i in range(1, n + 1): +        w[i], v[i] = list(map(int, input().split())) +    dp = [0] * (W + 1) +    for i in range(1, n + 1):  # i番目を見る +        newdp = dp[:] +        for j in range(W + 1): +            if j + w[i] <= W: +                newdp[j + w[i]] = max(newdp[j + w[i]], dp[j] + v[i]) +        dp = newdp +    print((dp[-1]))