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

I=[[*list(map(int,input().split()))]for _ in[0]*N]

I=[0]+I

C=[[0]*-~W for _ in[0]*-~N]

G=[[0]*-~W for _ in[0]*-~N]

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

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

  C[i][w]=C[i-1][w]

  if I[i][1]>w:continue

  if I[i][0]+C[i-1][w-I[i][1]]>C[i-1][w]:

   C[i][w]=I[i][0]+C[i-1][w-I[i][1]]

   G[i][w]=1

m=C[N][W]

w=W

D=[]

for i in range(N,0,-1):

 if G[i][w]:

  D+=[i]

  w-=I[i][1]

print((C[N][W]))

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

I=[0]+[[*list(map(int,input().split()))]for _ in[0]*N]

C=[[0]*-~W for _ in[0]*-~N]

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

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

  C[i][w]=C[i-1][w]

  if I[i][1]>w:continue

  if I[i][0]+C[i-1][w-I[i][1]]>C[i-1][w]:

   C[i][w]=I[i][0]+C[i-1][w-I[i][1]]

print((C[N][W]))

N, W = list(map(int, input().split()))
I = [[*list(map(int, input().split()))] for _ in [0] * N]
I = [0] + I
C = [[0] * -~W for _ in [0] * -~N]
G = [[0] * -~W for _ in [0] * -~N]
for i in range(1, N + 1):
    for w in range(1, W + 1):
        C[i][w] = C[i - 1][w]
        if I[i][1] > w:
            continue
        if I[i][0] + C[i - 1][w - I[i][1]] > C[i - 1][w]:
            C[i][w] = I[i][0] + C[i - 1][w - I[i][1]]
            G[i][w] = 1
m = C[N][W]
w = W
D = []
for i in range(N, 0, -1):
    if G[i][w]:
        D += [i]
        w -= I[i][1]
print((C[N][W]))

N, W = list(map(int, input().split()))
I = [0] + [[*list(map(int, input().split()))] for _ in [0] * N]
C = [[0] * -~W for _ in [0] * -~N]
for i in range(1, N + 1):
    for w in range(1, W + 1):
        C[i][w] = C[i - 1][w]
        if I[i][1] > w:
            continue
        if I[i][0] + C[i - 1][w - I[i][1]] > C[i - 1][w]:
            C[i][w] = I[i][0] + C[i - 1][w - I[i][1]]
print((C[N][W]))

-I = [[*list(map(int, input().split()))] for _ in [0] * N] -I = [0] + I +I = [0] + [[*list(map(int, input().split()))] for _ in [0] * N] -G = [[0] * -~W for _ in [0] * -~N] -            G[i][w] = 1 -m = C[N][W] -w = W -D = [] -for i in range(N, 0, -1): -    if G[i][w]: -        D += [i] -        w -= I[i][1]