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



Ws = []

Vs = []



for _ in range(N):

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

  Ws.append(w)

  Vs.append(v)





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



if Ws[0] <= W:

  for i in range(Ws[0], W+1):

    S[0][i] = Vs[0]



for weight in range(W+1):

  for item_num in range(N-1):

    if weight - Ws[item_num+1] < 0:

      S[item_num+1][weight] = max(S[item_num+1][weight], S[item_num][weight])

    else:

      S[item_num+1][weight] = max(S[item_num+1][weight], S[item_num][weight-Ws[item_num+1]] + Vs[item_num+1], S[item_num][weight])



print((max(S[N-1])))

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

Ws = []

Vs = []



for _ in range(N):

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

  Ws.append(w)

  Vs.append(v)



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



for i in range(W+1):

  if i >= Ws[0]:

    Ans[0][i] = Vs[0]



for i in range(1, N):

  for w in range(W+1):

    if w - Ws[i] >= 0:

      Ans[i][w] = max(Ans[i-1][w-Ws[i]] + Vs[i], Ans[i-1][w], Ans[i][w])

    else:

      Ans[i][w] = max(Ans[i-1][w], Ans[i][w])



print((max(Ans[N-1])))

N, W = list(map(int, input().split()))
Ws = []
Vs = []
for _ in range(N):
    w, v = list(map(int, input().split()))
    Ws.append(w)
    Vs.append(v)
S = [[0 for _ in range(W + 1)] for _ in range(N)]
if Ws[0] <= W:
    for i in range(Ws[0], W + 1):
        S[0][i] = Vs[0]
for weight in range(W + 1):
    for item_num in range(N - 1):
        if weight - Ws[item_num + 1] < 0:
            S[item_num + 1][weight] = max(S[item_num + 1][weight], S[item_num][weight])
        else:
            S[item_num + 1][weight] = max(
                S[item_num + 1][weight],
                S[item_num][weight - Ws[item_num + 1]] + Vs[item_num + 1],
                S[item_num][weight],
            )
print((max(S[N - 1])))

N, W = list(map(int, input().split()))
Ws = []
Vs = []
for _ in range(N):
    w, v = list(map(int, input().split()))
    Ws.append(w)
    Vs.append(v)
Ans = [[0 for _ in range(W + 1)] for _ in range(N)]
for i in range(W + 1):
    if i >= Ws[0]:
        Ans[0][i] = Vs[0]
for i in range(1, N):
    for w in range(W + 1):
        if w - Ws[i] >= 0:
            Ans[i][w] = max(Ans[i - 1][w - Ws[i]] + Vs[i], Ans[i - 1][w], Ans[i][w])
        else:
            Ans[i][w] = max(Ans[i - 1][w], Ans[i][w])
print((max(Ans[N - 1])))

-S = [[0 for _ in range(W + 1)] for _ in range(N)] -if Ws[0] <= W: -    for i in range(Ws[0], W + 1): -        S[0][i] = Vs[0] -for weight in range(W + 1): -    for item_num in range(N - 1): -        if weight - Ws[item_num + 1] < 0: -            S[item_num + 1][weight] = max(S[item_num + 1][weight], S[item_num][weight]) +Ans = [[0 for _ in range(W + 1)] for _ in range(N)] +for i in range(W + 1): +    if i >= Ws[0]: +        Ans[0][i] = Vs[0] +for i in range(1, N): +    for w in range(W + 1): +        if w - Ws[i] >= 0: +            Ans[i][w] = max(Ans[i - 1][w - Ws[i]] + Vs[i], Ans[i - 1][w], Ans[i][w]) -            S[item_num + 1][weight] = max( -                S[item_num + 1][weight], -                S[item_num][weight - Ws[item_num + 1]] + Vs[item_num + 1], -                S[item_num][weight], -            ) -print((max(S[N - 1]))) +            Ans[i][w] = max(Ans[i - 1][w], Ans[i][w]) +print((max(Ans[N - 1])))