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

Weight = [0]

Value = [0]



for i in range(N):

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

    Weight.append(w)

    Value.append(v)



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

for n in range(1, N + 1):

    for wei in range(W+1):

        if Weight[n] > wei:

            DP[n][wei] = DP[n-1][wei]

        else:

            DP[n][wei] = max(DP[n-1][wei], DP[n-1][wei - Weight[n]] + Value[n])

print((DP[N][W]))
N, W = list(map(int, input().split()))

Items = [tuple(map(int, input().split())) for _ in range(N)]

DP = [-1] * (W + 1)

DP[0] = 0



for w, v in Items:

    D = DP[:]

    for i, d in enumerate(DP):

        if d < 0:

            continue

        if i + w > W:

            break

        D[i + w] = max(D[i + w], d + v)

    DP = D

print((max(DP)))
N, W = list(map(int, input().split()))
Weight = [0]
Value = [0]
for i in range(N):
    w, v = list(map(int, input().split()))
    Weight.append(w)
    Value.append(v)
DP = [[0] * (W + 1) for i in range(N + 1)]
for n in range(1, N + 1):
    for wei in range(W + 1):
        if Weight[n] > wei:
            DP[n][wei] = DP[n - 1][wei]
        else:
            DP[n][wei] = max(DP[n - 1][wei], DP[n - 1][wei - Weight[n]] + Value[n])
print((DP[N][W]))

N, W = list(map(int, input().split()))
Items = [tuple(map(int, input().split())) for _ in range(N)]
DP = [-1] * (W + 1)
DP[0] = 0
for w, v in Items:
    D = DP[:]
    for i, d in enumerate(DP):
        if d < 0:
            continue
        if i + w > W:
            break
        D[i + w] = max(D[i + w], d + v)
    DP = D
print((max(DP)))

-Weight = [0] -Value = [0] -for i in range(N): -    w, v = list(map(int, input().split())) -    Weight.append(w) -    Value.append(v) -DP = [[0] * (W + 1) for i in range(N + 1)] -for n in range(1, N + 1): -    for wei in range(W + 1): -        if Weight[n] > wei: -            DP[n][wei] = DP[n - 1][wei] -        else: -            DP[n][wei] = max(DP[n - 1][wei], DP[n - 1][wei - Weight[n]] + Value[n]) -print((DP[N][W])) +Items = [tuple(map(int, input().split())) for _ in range(N)] +DP = [-1] * (W + 1) +DP[0] = 0 +for w, v in Items: +    D = DP[:] +    for i, d in enumerate(DP): +        if d < 0: +            continue +        if i + w > W: +            break +        D[i + w] = max(D[i + w], d + v) +    DP = D +print((max(DP)))