from collections import defaultdict



memo = {}

def dfs(i, w, item_list, W):

    if i >= len(item_list):

        return 0



    if (i, w) in memo:

        return memo[(i, w)]



    ans = 0

    # use

    new_w = w + item_list[i][1]

    if new_w <= W:

        ans = max(ans, dfs(i + 1, new_w, item_list, W) + item_list[i][0])



    # not use

    ans = max(ans, dfs(i + 1, w, item_list, W))



    memo[(i, w)] = ans

    return ans





def main():

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

    item_list = []

    for _ in range(N):

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

        item_list.append((v, w))



    print((dfs(0, 0, item_list, W)))



if __name__ == '__main__':

    main()
from collections import defaultdict





def solve(N, W, vs, ws):

    dp = [[0] * (W + 1) for _ in range(N + 1)]

    for i in range(N):

        v, w = vs[i], ws[i]

        for j in range(len(dp[0])):

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

            if j + w < len(dp[0]):

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

    ans = 0

    for line in dp:

        ans = max(line)

    return ans





def main():

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

    vs, ws = [], []

    for _ in range(N):

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

        vs.append(v)

        ws.append(w)



    print((solve(N, W, vs, ws)))



if __name__ == '__main__':

    main()
from collections import defaultdict

memo = {}


def dfs(i, w, item_list, W):
    if i >= len(item_list):
        return 0
    if (i, w) in memo:
        return memo[(i, w)]
    ans = 0
    # use
    new_w = w + item_list[i][1]
    if new_w <= W:
        ans = max(ans, dfs(i + 1, new_w, item_list, W) + item_list[i][0])
    # not use
    ans = max(ans, dfs(i + 1, w, item_list, W))
    memo[(i, w)] = ans
    return ans


def main():
    N, W = list(map(int, input().split()))
    item_list = []
    for _ in range(N):
        v, w = list(map(int, input().split()))
        item_list.append((v, w))
    print((dfs(0, 0, item_list, W)))


if __name__ == "__main__":
    main()

from collections import defaultdict


def solve(N, W, vs, ws):
    dp = [[0] * (W + 1) for _ in range(N + 1)]
    for i in range(N):
        v, w = vs[i], ws[i]
        for j in range(len(dp[0])):
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
            if j + w < len(dp[0]):
                dp[i + 1][j + w] = max(dp[i + 1][j + w], dp[i][j] + v)
    ans = 0
    for line in dp:
        ans = max(line)
    return ans


def main():
    N, W = list(map(int, input().split()))
    vs, ws = [], []
    for _ in range(N):
        v, w = list(map(int, input().split()))
        vs.append(v)
        ws.append(w)
    print((solve(N, W, vs, ws)))


if __name__ == "__main__":
    main()

-memo = {} - -def dfs(i, w, item_list, W): -    if i >= len(item_list): -        return 0 -    if (i, w) in memo: -        return memo[(i, w)] +def solve(N, W, vs, ws): +    dp = [[0] * (W + 1) for _ in range(N + 1)] +    for i in range(N): +        v, w = vs[i], ws[i] +        for j in range(len(dp[0])): +            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]) +            if j + w < len(dp[0]): +                dp[i + 1][j + w] = max(dp[i + 1][j + w], dp[i][j] + v) -    # use -    new_w = w + item_list[i][1] -    if new_w <= W: -        ans = max(ans, dfs(i + 1, new_w, item_list, W) + item_list[i][0]) -    # not use -    ans = max(ans, dfs(i + 1, w, item_list, W)) -    memo[(i, w)] = ans +    for line in dp: +        ans = max(line) -    item_list = [] +    vs, ws = [], [] -        item_list.append((v, w)) -    print((dfs(0, 0, item_list, W))) +        vs.append(v) +        ws.append(w) +    print((solve(N, W, vs, ws)))