# coding: utf-8











import math

import string

import itertools

import fractions

import heapq

import collections

import re

import array

import bisect



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-1, j-w[i-1]) + v[i-1])

    return dpt[i][j]



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



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

    return [[init for _ in range(d2)] for _ in range(d1)]





def solve(N, W, v, w):

    # dp[i][k]: 0~i?????????item????????????????????????????????????k??¨??????????????????????????´??????max value

    # return: max(dp[N-1][*])

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

    # dp[i][0] = 0, dp[0][k] = 0(k<w[0]), v[0](otherwise)

    dp = array2d(N, W + 1)

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

        dp[0][k] = 0 if k < w[0] else v[0]

    for i in range(1, N):

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

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

            if k - w[i] >= 0:

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

    return max(dp[-1])







def main():

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

    v = [None] * N

    w = [None] * N

    for i in range(N):

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

    print((solve(N, W, v, w)))



main()
# coding: utf-8
import math
import string
import itertools
import fractions
import heapq
import collections
import re
import array
import bisect


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 - 1, j - w[i - 1]) + v[i - 1])
    return dpt[i][j]


print(dp(N, W))

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


def solve(N, W, v, w):
    # dp[i][k]: 0~i?????????item????????????????????????????????????k??¨??????????????????????????´??????max value
    # return: max(dp[N-1][*])
    # dp[i][k] = max(dp[i-1][k], dp[i-1][k-w[i]] + v[i])
    # dp[i][0] = 0, dp[0][k] = 0(k<w[0]), v[0](otherwise)
    dp = array2d(N, W + 1)
    for k in range(0, W + 1):
        dp[0][k] = 0 if k < w[0] else v[0]
    for i in range(1, N):
        for k in range(0, W + 1):
            dp[i][k] = dp[i - 1][k]
            if k - w[i] >= 0:
                dp[i][k] = max(dp[i][k], dp[i - 1][k - w[i]] + v[i])
    return max(dp[-1])


def main():
    N, W = list(map(int, input().split()))
    v = [None] * N
    w = [None] * N
    for i in range(N):
        v[i], w[i] = list(map(int, input().split()))
    print((solve(N, W, v, w)))


main()

-import math -import string -import itertools -import fractions -import heapq -import collections -import re -import array -import bisect +def array2d(d1, d2, init=None): +    return [[init for _ in range(d2)] for _ in range(d1)] -def array2d(row, col, init=None): -    return [[init for _ in range(col)] for _ in range(row)] +def solve(N, W, v, w): +    # dp[i][k]: 0~i?????????item????????????????????????????????????k??¨??????????????????????????´??????max value +    # return: max(dp[N-1][*]) +    # dp[i][k] = max(dp[i-1][k], dp[i-1][k-w[i]] + v[i]) +    # dp[i][0] = 0, dp[0][k] = 0(k<w[0]), v[0](otherwise) +    dp = array2d(N, W + 1) +    for k in range(0, W + 1): +        dp[0][k] = 0 if k < w[0] else v[0] +    for i in range(1, N): +        for k in range(0, W + 1): +            dp[i][k] = dp[i - 1][k] +            if k - w[i] >= 0: +                dp[i][k] = max(dp[i][k], dp[i - 1][k - w[i]] + v[i]) +    return max(dp[-1]) -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 main(): +    N, W = list(map(int, input().split())) +    v = [None] * N +    w = [None] * N +    for i in range(N): +        v[i], w[i] = list(map(int, input().split())) +    print((solve(N, W, v, w))) -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 - 1, j - w[i - 1]) + v[i - 1]) -    return dpt[i][j] - - -print(dp(N, W)) +main()