# what is dp relation 

# dp[n][w]=max(dp[n-1][w-wt[n]]+p[n],dp[n-1][w])



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

wt,p=[],[]

for _ in range(n):

    a,b=list(map(int,input().split()))

    wt.append(a)

    p.append(b)

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

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

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

        if wt[x-1]<=y:

            dp[x][y]=max(dp[x-1][y-wt[x-1]]+p[x-1],dp[x-1][y])

        else:

            dp[x][y]=dp[x-1][y]

print((dp[-1][-1]))
n,W=list(map(int,input().split()))

wt,p=[],[]

for _ in range(n):

    a,b=list(map(int,input().split()))

    wt.append(a)

    p.append(b)

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

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

  

  for y in range(W,0,-1):

    if wt[x-1]<=y:

        

      dp[y]=max(dp[y-wt[x-1]]+p[x-1],dp[y])

    else:



      dp[y]=dp[y]

print((dp[-1]))
# what is dp relation
# dp[n][w]=max(dp[n-1][w-wt[n]]+p[n],dp[n-1][w])
n, W = list(map(int, input().split()))
wt, p = [], []
for _ in range(n):
    a, b = list(map(int, input().split()))
    wt.append(a)
    p.append(b)
dp = [[0 for i in range(W + 1)] for j in range(n + 1)]
for x in range(1, n + 1):
    for y in range(1, W + 1):
        if wt[x - 1] <= y:
            dp[x][y] = max(dp[x - 1][y - wt[x - 1]] + p[x - 1], dp[x - 1][y])
        else:
            dp[x][y] = dp[x - 1][y]
print((dp[-1][-1]))

n, W = list(map(int, input().split()))
wt, p = [], []
for _ in range(n):
    a, b = list(map(int, input().split()))
    wt.append(a)
    p.append(b)
dp = [0 for i in range(W + 1)]
for x in range(1, n + 1):
    for y in range(W, 0, -1):
        if wt[x - 1] <= y:
            dp[y] = max(dp[y - wt[x - 1]] + p[x - 1], dp[y])
        else:
            dp[y] = dp[y]
print((dp[-1]))

-# what is dp relation -# dp[n][w]=max(dp[n-1][w-wt[n]]+p[n],dp[n-1][w]) -dp = [[0 for i in range(W + 1)] for j in range(n + 1)] +dp = [0 for i in range(W + 1)] -    for y in range(1, W + 1): +    for y in range(W, 0, -1): -            dp[x][y] = max(dp[x - 1][y - wt[x - 1]] + p[x - 1], dp[x - 1][y]) +            dp[y] = max(dp[y - wt[x - 1]] + p[x - 1], dp[y]) -            dp[x][y] = dp[x - 1][y] -print((dp[-1][-1])) +            dp[y] = dp[y] +print((dp[-1]))