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

wv = [list(map(int, input().split())) for _ in range(n)]

w = [wv[i][0] for i in range(n)]

v = [wv[i][1] for i in range(n)]

inf = float('inf')

# dp[i][weight] 

# := i-1番目までの品物で重さweightを超えないように選んだときの価値の総和の最大値

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

for i in range(n):

    for sum_w in range(W+1):

        if sum_w - w[i] >= 0:

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

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

print((dp[n][W]))

def main():

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

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

    w = [wv[i][0] for i in range(N)]

    v = [wv[i][1] for i in range(N)]

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

    

    for i in range(N):

        for weight in range(W+1):

            # 品物iを（選べるなら）選ぶ

            if weight >= w[i]: vdp[i+1][weight] = max(vdp[i][weight - w[i]] + v[i], vdp[i][weight])

            # 品物iを選ばない

            vdp[i+1][weight] = max(vdp[i+1][weight], vdp[i][weight])

    print((vdp[N][W]))



if __name__ == '__main__':

    main()
n, W = list(map(int, input().split()))
wv = [list(map(int, input().split())) for _ in range(n)]
w = [wv[i][0] for i in range(n)]
v = [wv[i][1] for i in range(n)]
inf = float("inf")
# dp[i][weight]
# := i-1番目までの品物で重さweightを超えないように選んだときの価値の総和の最大値
dp = [[0 for _ in range(W + 1)] for _ in range(n + 1)]
for i in range(n):
    for sum_w in range(W + 1):
        if sum_w - w[i] >= 0:
            dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w - w[i]] + v[i])
        dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w])
print((dp[n][W]))

def main():
    N, W = list(map(int, input().split()))
    wv = [list(map(int, input().split())) for _ in range(N)]
    w = [wv[i][0] for i in range(N)]
    v = [wv[i][1] for i in range(N)]
    vdp = [[0 for _ in range(W + 1)] for _ in range(N + 1)]
    for i in range(N):
        for weight in range(W + 1):
            # 品物iを（選べるなら）選ぶ
            if weight >= w[i]:
                vdp[i + 1][weight] = max(vdp[i][weight - w[i]] + v[i], vdp[i][weight])
            # 品物iを選ばない
            vdp[i + 1][weight] = max(vdp[i + 1][weight], vdp[i][weight])
    print((vdp[N][W]))


if __name__ == "__main__":
    main()

-n, W = list(map(int, input().split())) -wv = [list(map(int, input().split())) for _ in range(n)] -w = [wv[i][0] for i in range(n)] -v = [wv[i][1] for i in range(n)] -inf = float("inf") -# dp[i][weight] -# := i-1番目までの品物で重さweightを超えないように選んだときの価値の総和の最大値 -dp = [[0 for _ in range(W + 1)] for _ in range(n + 1)] -for i in range(n): -    for sum_w in range(W + 1): -        if sum_w - w[i] >= 0: -            dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w - w[i]] + v[i]) -        dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w]) -print((dp[n][W])) +def main(): +    N, W = list(map(int, input().split())) +    wv = [list(map(int, input().split())) for _ in range(N)] +    w = [wv[i][0] for i in range(N)] +    v = [wv[i][1] for i in range(N)] +    vdp = [[0 for _ in range(W + 1)] for _ in range(N + 1)] +    for i in range(N): +        for weight in range(W + 1): +            # 品物iを（選べるなら）選ぶ +            if weight >= w[i]: +                vdp[i + 1][weight] = max(vdp[i][weight - w[i]] + v[i], vdp[i][weight]) +            # 品物iを選ばない +            vdp[i + 1][weight] = max(vdp[i + 1][weight], vdp[i][weight]) +    print((vdp[N][W])) + + +if __name__ == "__main__": +    main()