# coding: utf-8













def array2d(row, col, init = None):

    return [[init for _ in range(col)] for _ in range(row)]



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

v = []

w = []

for i in range(N):

    vi, wi = list(map(int, input().split(" ")))

    v.append(vi)

    w.append(wi)



dpt = array2d(N + 1, W + 1)



def dp(i, j):

    if dpt[i][j] is not None:

        return dpt[i][j]

    if i == 0:

        dpt[i][j] = 0

        return 0

    if j < w[i-1]:

        dpt[i][j] = dp(i-1, j)

        return dpt[i][j]

    dpt[i][j] = max(dp(i-1, j), dp(i, j-w[i-1]) + v[i-1])

    return dpt[i][j]



for i in range(N + 1):

    for j in range(W + 1):

        dp(i, j)

print(dp(N, W))
# coding: utf-8

"""docstring"""





def arr2d(d1, d2, init=None):

    return [[init for i in range(d2)] for j in range(d1)]





def solve(N, W):

    v = [None] * N

    w = [None] * N

    for i in range(N):

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



    # dp[i][j]: item 0..i ??????weight sum <= j ??¨????????????????????¶????????§????????§???value sum

    # (i: 0..N-1, j: 0..W)

    dp = arr2d(N, W + 1, 0)

    # i==0

    for j in range(0, W + 1):

        dp[0][j] = (j // w[0]) * v[0]

    for i in range(1, N):

        for j in range(0, W + 1):

            dp[i][j] = dp[i-1][j]

            if j >= w[i]:

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

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

    return dp[-1][-1]





def main():

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

    print((solve(n, w)))





if __name__ == "__main__":

    main()
# coding: utf-8
def array2d(row, col, init=None):
    return [[init for _ in range(col)] for _ in range(row)]


N, W = list(map(int, input().split(" ")))
v = []
w = []
for i in range(N):
    vi, wi = list(map(int, input().split(" ")))
    v.append(vi)
    w.append(wi)
dpt = array2d(N + 1, W + 1)


def dp(i, j):
    if dpt[i][j] is not None:
        return dpt[i][j]
    if i == 0:
        dpt[i][j] = 0
        return 0
    if j < w[i - 1]:
        dpt[i][j] = dp(i - 1, j)
        return dpt[i][j]
    dpt[i][j] = max(dp(i - 1, j), dp(i, j - w[i - 1]) + v[i - 1])
    return dpt[i][j]


for i in range(N + 1):
    for j in range(W + 1):
        dp(i, j)
print(dp(N, W))

# coding: utf-8
"""docstring"""


def arr2d(d1, d2, init=None):
    return [[init for i in range(d2)] for j in range(d1)]


def solve(N, W):
    v = [None] * N
    w = [None] * N
    for i in range(N):
        v[i], w[i] = list(map(int, input().split()))
    # dp[i][j]: item 0..i ??????weight sum <= j ??¨????????????????????¶????????§????????§???value sum
    # (i: 0..N-1, j: 0..W)
    dp = arr2d(N, W + 1, 0)
    # i==0
    for j in range(0, W + 1):
        dp[0][j] = (j // w[0]) * v[0]
    for i in range(1, N):
        for j in range(0, W + 1):
            dp[i][j] = dp[i - 1][j]
            if j >= w[i]:
                dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i]] + v[i])
                dp[i][j] = max(dp[i][j], dp[i][j - w[i]] + v[i])
    return dp[-1][-1]


def main():
    n, w = list(map(int, input().split()))
    print((solve(n, w)))


if __name__ == "__main__":
    main()

-def array2d(row, col, init=None): -    return [[init for _ in range(col)] for _ in range(row)] +"""docstring""" -N, W = list(map(int, input().split(" "))) -v = [] -w = [] -for i in range(N): -    vi, wi = list(map(int, input().split(" "))) -    v.append(vi) -    w.append(wi) -dpt = array2d(N + 1, W + 1) +def arr2d(d1, d2, init=None): +    return [[init for i in range(d2)] for j in range(d1)] -def dp(i, j): -    if dpt[i][j] is not None: -        return dpt[i][j] -    if i == 0: -        dpt[i][j] = 0 -        return 0 -    if j < w[i - 1]: -        dpt[i][j] = dp(i - 1, j) -        return dpt[i][j] -    dpt[i][j] = max(dp(i - 1, j), dp(i, j - w[i - 1]) + v[i - 1]) -    return dpt[i][j] +def solve(N, W): +    v = [None] * N +    w = [None] * N +    for i in range(N): +        v[i], w[i] = list(map(int, input().split())) +    # dp[i][j]: item 0..i ??????weight sum <= j ??¨????????????????????¶????????§????????§???value sum +    # (i: 0..N-1, j: 0..W) +    dp = arr2d(N, W + 1, 0) +    # i==0 +    for j in range(0, W + 1): +        dp[0][j] = (j // w[0]) * v[0] +    for i in range(1, N): +        for j in range(0, W + 1): +            dp[i][j] = dp[i - 1][j] +            if j >= w[i]: +                dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i]] + v[i]) +                dp[i][j] = max(dp[i][j], dp[i][j - w[i]] + v[i]) +    return dp[-1][-1] -for i in range(N + 1): -    for j in range(W + 1): -        dp(i, j) -print(dp(N, W)) +def main(): +    n, w = list(map(int, input().split())) +    print((solve(n, w))) + + +if __name__ == "__main__": +    main()