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]))
# 0-1 Knapsack Problem

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 i in range(N):

    v, w = items[i]

    for j in range(W, w-1, -1):

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



print((DP[-1]))
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]))

# 0-1 Knapsack Problem
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 i in range(N):
    v, w = items[i]
    for j in range(W, w - 1, -1):
        DP[j] = max(DP[j], v + DP[j - w])
print((DP[-1]))

+# 0-1 Knapsack Problem -DP = [[0] * (W + 1) for _ in range(N + 1)] -# DP[i+1][j] = max(DP[i][j], v + DP[i][j-w]) +DP = [0] * (W + 1) -    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])) +    v, w = items[i] +    for j in range(W, w - 1, -1): +        DP[j] = max(DP[j], v + DP[j - w]) +print((DP[-1]))