M = {}



N, W = [int(x) for x in input().split()]

items = []

for i in range(N):

    items.append(tuple(int(x) for x in input().split()))





def dfs(i, j):

    if (i, j) in M:

        return M[i, j]

    if i == N:

        return 0



    v, w = items[i]

    if w <= j:

        r = max(dfs(i+1, j), v + dfs(i+1, j-w))

    else:

        r = dfs(i+1, j)

    M[i, j] = r

    return r





print((dfs(0, W)))
N, W = [int(x) for x in input().split()]

items = []

for i in range(N):

    items.append(tuple(int(x) for x in input().split()))





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

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

for i in range(N):

    for j in range(W+1):

        v, w = items[i]

        if w <= j:

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

        else:

            DP[i+1][j] = DP[i][j]



print((DP[-1][-1]))
M = {}
N, W = [int(x) for x in input().split()]
items = []
for i in range(N):
    items.append(tuple(int(x) for x in input().split()))


def dfs(i, j):
    if (i, j) in M:
        return M[i, j]
    if i == N:
        return 0
    v, w = items[i]
    if w <= j:
        r = max(dfs(i + 1, j), v + dfs(i + 1, j - w))
    else:
        r = dfs(i + 1, j)
    M[i, j] = r
    return r


print((dfs(0, W)))

N, W = [int(x) for x in input().split()]
items = []
for i in range(N):
    items.append(tuple(int(x) for x in input().split()))
DP = [[0] * (W + 1) for _ in range(N + 1)]
# DP[i+1][j] = max(DP[i][j], v + DP[i][j-w])
for i in range(N):
    for j in range(W + 1):
        v, w = items[i]
        if w <= j:
            DP[i + 1][j] = max(DP[i][j], v + DP[i][j - w])
        else:
            DP[i + 1][j] = DP[i][j]
print((DP[-1][-1]))

-M = {} - - -def dfs(i, j): -    if (i, j) in M: -        return M[i, j] -    if i == N: -        return 0 -    v, w = items[i] -    if w <= j: -        r = max(dfs(i + 1, j), v + dfs(i + 1, j - w)) -    else: -        r = dfs(i + 1, j) -    M[i, j] = r -    return r - - -print((dfs(0, W))) +DP = [[0] * (W + 1) for _ in range(N + 1)] +# DP[i+1][j] = max(DP[i][j], v + DP[i][j-w]) +for i in range(N): +    for j in range(W + 1): +        v, w = items[i] +        if w <= j: +            DP[i + 1][j] = max(DP[i][j], v + DP[i][j - w]) +        else: +            DP[i + 1][j] = DP[i][j] +print((DP[-1][-1]))