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

dp = [[0]*100100 for _ in range(110)]



for i in range(N):

    weight, value = list(map(int, input().split()))

    for sum_w in range(W+1):

        if sum_w - weight >= 0:

            dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w - weight] + value)



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



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



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



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

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

    for j in range(1,  W + 1):

        if j >= w:

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

        else:

            dp[i][j] = dp[i - 1][j]



print((dp[N][W]))
N, W = list(map(int, input().split()))
dp = [[0] * 100100 for _ in range(110)]
for i in range(N):
    weight, value = list(map(int, input().split()))
    for sum_w in range(W + 1):
        if sum_w - weight >= 0:
            dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w - weight] + value)
        dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w])
print((dp[N][W]))

N, W = list(map(int, input().split()))
dp = [[0] * (W + 1) for i in range(N + 1)]
for i in range(1, N + 1):
    w, v = list(map(int, input().split()))
    for j in range(1, W + 1):
        if j >= w:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v)
        else:
            dp[i][j] = dp[i - 1][j]
print((dp[N][W]))

-dp = [[0] * 100100 for _ in range(110)] -for i in range(N): -    weight, value = list(map(int, input().split())) -    for sum_w in range(W + 1): -        if sum_w - weight >= 0: -            dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w - weight] + value) -        dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w]) +dp = [[0] * (W + 1) for i in range(N + 1)] +for i in range(1, N + 1): +    w, v = list(map(int, input().split())) +    for j in range(1, W + 1): +        if j >= w: +            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v) +        else: +            dp[i][j] = dp[i - 1][j]