from sys import stdin

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

k=[[0 for i in range(W+1)] for i in range(2)]

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

    w,v=list(map(int,stdin.readline().split()))

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

        if w<=j:

            k[1][j]=max(v+k[0][j-w],k[0][j])

        else:

            k[1][j]=k[0][j]

    k[0]=[i for i in k[1]]

    k[1]=[0]*(W+1)

print((k[0][-1]))
from sys import stdin

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

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

for i in range(n):

    w,v=list(map(int,stdin.readline().split()))

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

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

print((dp[-1]))
from sys import stdin

n, W = list(map(int, input().split()))
k = [[0 for i in range(W + 1)] for i in range(2)]
for i in range(1, n + 1):
    w, v = list(map(int, stdin.readline().split()))
    for j in range(1, W + 1):
        if w <= j:
            k[1][j] = max(v + k[0][j - w], k[0][j])
        else:
            k[1][j] = k[0][j]
    k[0] = [i for i in k[1]]
    k[1] = [0] * (W + 1)
print((k[0][-1]))

from sys import stdin

n, W = list(map(int, input().split()))
dp = [0 for i in range(W + 1)]
for i in range(n):
    w, v = list(map(int, stdin.readline().split()))
    for j in range(W - w, -1, -1):
        dp[j + w] = max(dp[j] + v, dp[j + w])
print((dp[-1]))

-k = [[0 for i in range(W + 1)] for i in range(2)] -for i in range(1, n + 1): +dp = [0 for i in range(W + 1)] +for i in range(n): -    for j in range(1, W + 1): -        if w <= j: -            k[1][j] = max(v + k[0][j - w], k[0][j]) -        else: -            k[1][j] = k[0][j] -    k[0] = [i for i in k[1]] -    k[1] = [0] * (W + 1) -print((k[0][-1])) +    for j in range(W - w, -1, -1): +        dp[j + w] = max(dp[j] + v, dp[j + w]) +print((dp[-1]))