import sys

sys.setrecursionlimit(2147483647)

INF=float("inf")

MOD=10**9+7

def make_v(*args,e=0):

    from copy import deepcopy

    A=e

    for i in args[::-1]: A=[deepcopy(A) for _ in range(i)]

    return A

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

def resolve():

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

    W=[0]*(n+1)

    V=[0]*(n+1)

    for i in range(n):

        W[i+1],V[i+1]=list(map(int,input().split()))

    dp=make_v(n+1,w+1)

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

        for k in range(w+1):

            if(k-W[i]>=0):

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

            else:

                dp[i][k]=dp[i-1][k]

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

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+1)

    V=[0]*(n+1)

    for i in range(n):

        W[i+1],V[i+1]=list(map(int,input().split()))

    dp=[[0]*(w+1) for _ in range(n+1)]

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

        for k in range(w+1):

            if(k-W[i]>=0):

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

            else:

                dp[i][k]=dp[i-1][k]

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

resolve()
import sys

sys.setrecursionlimit(2147483647)
INF = float("inf")
MOD = 10**9 + 7


def make_v(*args, e=0):
    from copy import deepcopy

    A = e
    for i in args[::-1]:
        A = [deepcopy(A) for _ in range(i)]
    return A


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


def resolve():
    n, w = list(map(int, input().split()))
    W = [0] * (n + 1)
    V = [0] * (n + 1)
    for i in range(n):
        W[i + 1], V[i + 1] = list(map(int, input().split()))
    dp = make_v(n + 1, w + 1)
    for i in range(1, n + 1):
        for k in range(w + 1):
            if k - W[i] >= 0:
                dp[i][k] = max(dp[i - 1][k - W[i]] + V[i], dp[i - 1][k])
            else:
                dp[i][k] = dp[i - 1][k]
    print((dp[n][w]))


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 + 1)
    V = [0] * (n + 1)
    for i in range(n):
        W[i + 1], V[i + 1] = list(map(int, input().split()))
    dp = [[0] * (w + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for k in range(w + 1):
            if k - W[i] >= 0:
                dp[i][k] = max(dp[i - 1][k - W[i]] + V[i], dp[i - 1][k])
            else:
                dp[i][k] = dp[i - 1][k]
    print((dp[n][w]))


resolve()

- - -def make_v(*args, e=0): -    from copy import deepcopy - -    A = e -    for i in args[::-1]: -        A = [deepcopy(A) for _ in range(i)] -    return A - - -    dp = make_v(n + 1, w + 1) +    dp = [[0] * (w + 1) for _ in range(n + 1)]