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

cost=[[0 for i in range(w+1)] for j in range(n+1)]

value=[tuple(map(int,input().split())) for i in range(n)]

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

  for j in range(w+1):

    weight_=value[i-1][0]

    value_=value[i-1][1]

    if j < weight_:

      cost[i][j]=cost[i-1][j]

    else:

      cost[i][j]=max(cost[i-1][j-weight_]+value_,cost[i-1][j])

print((cost[-1][-1]))

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

cost=[[0 for i in range(w+1)] for j in range(n+1)] #DP配列です

value=[tuple(map(int,input().split())) for i in range(n)]#品物の情報を受けとります

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

  for j in range(w+1):

    weight_=value[i-1][0] #i-1番目の品物の重さ

    value_=value[i-1][1] #i-1番目の品物の価値

    if j < weight_:

      cost[i][j]=cost[i-1][j]

    else:

      cost[i][j]=max(cost[i-1][j-weight_]+value_,cost[i-1][j])

print((cost[n][w]))

n, w = list(map(int, input().split()))
cost = [[0 for i in range(w + 1)] for j in range(n + 1)]
value = [tuple(map(int, input().split())) for i in range(n)]
for i in range(1, n + 1):
    for j in range(w + 1):
        weight_ = value[i - 1][0]
        value_ = value[i - 1][1]
        if j < weight_:
            cost[i][j] = cost[i - 1][j]
        else:
            cost[i][j] = max(cost[i - 1][j - weight_] + value_, cost[i - 1][j])
print((cost[-1][-1]))

n, w = list(map(int, input().split()))
cost = [[0 for i in range(w + 1)] for j in range(n + 1)]  # DP配列です
value = [tuple(map(int, input().split())) for i in range(n)]  # 品物の情報を受けとります
for i in range(1, n + 1):
    for j in range(w + 1):
        weight_ = value[i - 1][0]  # i-1番目の品物の重さ
        value_ = value[i - 1][1]  # i-1番目の品物の価値
        if j < weight_:
            cost[i][j] = cost[i - 1][j]
        else:
            cost[i][j] = max(cost[i - 1][j - weight_] + value_, cost[i - 1][j])
print((cost[n][w]))

-cost = [[0 for i in range(w + 1)] for j in range(n + 1)] -value = [tuple(map(int, input().split())) for i in range(n)] +cost = [[0 for i in range(w + 1)] for j in range(n + 1)]  # DP配列です +value = [tuple(map(int, input().split())) for i in range(n)]  # 品物の情報を受けとります -        weight_ = value[i - 1][0] -        value_ = value[i - 1][1] +        weight_ = value[i - 1][0]  # i-1番目の品物の重さ +        value_ = value[i - 1][1]  # i-1番目の品物の価値 -print((cost[-1][-1])) +print((cost[n][w]))