def knapsack(N,W,weight,value):

    #初期化

    inf=float("inf")

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

    for i in range(W+1): 

        dp[0][i]=0

    #DP

    for i in range(N):

        for w in range(W+1):

            if weight[i]<=w: #dp[i][w-weight[i]の状態にi番目の荷物が入る可能性がある

                dp[i+1][w]=max(dp[i][w-weight[i]]+value[i], dp[i][w])

            else: #入る可能性はない

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

    return dp[N][W]



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

weight=[0]*n

value=[0]*n

for i in range(n):

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



print((knapsack(n,w,weight,value)))
n,w=list(map(int,input().split()))

weight=[]

value=[]

for i in range(n):

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

    weight.append(x)

    value.append(v)

    

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



for i in range(n):

    for j in range(w+1):

        

        if j+weight[i]<=w :

            dp[i+1][j+weight[i]]=max(dp[i+1][j+weight[i]],dp[i][j]+value[i])

        

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



print((dp[-1][-1]))
def knapsack(N, W, weight, value):
    # 初期化
    inf = float("inf")
    dp = [[-inf for i in range(W + 1)] for j in range(N + 1)]
    for i in range(W + 1):
        dp[0][i] = 0
    # DP
    for i in range(N):
        for w in range(W + 1):
            if weight[i] <= w:  # dp[i][w-weight[i]の状態にi番目の荷物が入る可能性がある
                dp[i + 1][w] = max(dp[i][w - weight[i]] + value[i], dp[i][w])
            else:  # 入る可能性はない
                dp[i + 1][w] = dp[i][w]
    return dp[N][W]


n, w = list(map(int, input().split()))
weight = [0] * n
value = [0] * n
for i in range(n):
    weight[i], value[i] = list(map(int, input().split()))
print((knapsack(n, w, weight, value)))

n, w = list(map(int, input().split()))
weight = []
value = []
for i in range(n):
    x, v = list(map(int, input().split()))
    weight.append(x)
    value.append(v)
dp = [[0 for i in range(w + 1)] for i in range(n + 1)]
for i in range(n):
    for j in range(w + 1):
        if j + weight[i] <= w:
            dp[i + 1][j + weight[i]] = max(
                dp[i + 1][j + weight[i]], dp[i][j] + value[i]
            )
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
print((dp[-1][-1]))

-def knapsack(N, W, weight, value): -    # 初期化 -    inf = float("inf") -    dp = [[-inf for i in range(W + 1)] for j in range(N + 1)] -    for i in range(W + 1): -        dp[0][i] = 0 -    # DP -    for i in range(N): -        for w in range(W + 1): -            if weight[i] <= w:  # dp[i][w-weight[i]の状態にi番目の荷物が入る可能性がある -                dp[i + 1][w] = max(dp[i][w - weight[i]] + value[i], dp[i][w]) -            else:  # 入る可能性はない -                dp[i + 1][w] = dp[i][w] -    return dp[N][W] - - -weight = [0] * n -value = [0] * n +weight = [] +value = [] -    weight[i], value[i] = list(map(int, input().split())) -print((knapsack(n, w, weight, value))) +    x, v = list(map(int, input().split())) +    weight.append(x) +    value.append(v) +dp = [[0 for i in range(w + 1)] for i in range(n + 1)] +for i in range(n): +    for j in range(w + 1): +        if j + weight[i] <= w: +            dp[i + 1][j + weight[i]] = max( +                dp[i + 1][j + weight[i]], dp[i][j] + value[i] +            ) +        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]) +print((dp[-1][-1]))