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

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

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



for i in range(N):

  wv[i] = list(map(int, input().split()))



for i in range(N):

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

    if w < wv[i][0]:

      dp[w][i+1] = dp[w][i]

    else:

      dp[w][i+1] = max(dp[w-wv[i][0]][i]+wv[i][1], dp[w][i])



print((dp[-1][-1]))

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

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



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



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

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

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

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

    else:

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

      

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

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

-wv = [[0 for i in range(2)] for j in range(N)] -dp = [[0 for i in range(N + 1)] for j in range(W + 1)] -for i in range(N): -    wv[i] = list(map(int, input().split())) -for i in range(N): -    for w in range(1, W + 1): -        if w < wv[i][0]: -            dp[w][i + 1] = dp[w][i] +wv = [tuple(map(int, input().split())) for _ in range(N)] +dp = [[0] * (W + 1) for _ in range(N + 1)] +for i in range(1, N + 1): +    for j in range(1, W + 1): +        if j >= wv[i - 1][0]: +            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - wv[i - 1][0]] + wv[i - 1][1]) -            dp[w][i + 1] = max(dp[w - wv[i][0]][i] + wv[i][1], dp[w][i]) +            dp[i][j] = dp[i - 1][j]