INF = 10 ** 12



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



items =[] * N



for i in range(N):

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

    items.append([v,w])



dp = [[INF for i in range(W+1)] for j in range(N+1)]



for i in range(W+1):

    dp[0][i] = 0



for i in range(N+1):

    dp[i][0] = 0



for i in range(1,N+1): #1<= i <= N

    for j in range(1, W+1): # 1 <= j <= W

        if j - items[i-1][1] >= 0:

            dp[i][j] = max(dp[i-1][j], dp[i-1][j - items[i-1][1]] + items[i-1][0])

        else:

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



print((dp[N][W]))

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

 

INF = 10**10

#dp = [[INF]*100000]*(N*100)#余分に

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



for i in range (N):

    dp[i][0] =0

for j in range (W+1):

    dp[0][j] =0

    



for i in range (N):

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

    for j in range (W+1):

        if j-w>=0:

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

        else:

            dp[i+1][j] = dp[i][j]





print((dp[N][W]))

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

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

-INF = 10**12 -items = [] * N +INF = 10**10 +# dp = [[INF]*100000]*(N*100)#余分に +dp = [[0 for i in range(W + 1)] for j in range(N + 1)] +for i in range(N): +    dp[i][0] = 0 +for j in range(W + 1): +    dp[0][j] = 0 -    items.append([v, w]) -dp = [[INF for i in range(W + 1)] for j in range(N + 1)] -for i in range(W + 1): -    dp[0][i] = 0 -for i in range(N + 1): -    dp[i][0] = 0 -for i in range(1, N + 1):  # 1<= i <= N -    for j in range(1, W + 1):  # 1 <= j <= W -        if j - items[i - 1][1] >= 0: -            dp[i][j] = max( -                dp[i - 1][j], dp[i - 1][j - items[i - 1][1]] + items[i - 1][0] -            ) +    for j in range(W + 1): +        if j - w >= 0: +            dp[i + 1][j] = max(dp[i][j], dp[i][j - w] + v) -            dp[i][j] = dp[i - 1][j] +            dp[i + 1][j] = dp[i][j]