def knapsack_1(N, W, lst):

    #N : 品物数

    #W : 重みの総和

    #lst (wi,vi) : 商品iの重みwi、価値vi

    

    #dp[i][j] : i番目の品物から重さの総和がj以下になるように選んだ場合の価値の総和の最大値

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

    

    for i in range(N):

        for j in range(W+1):

            if j < lst[i][0]:

                dp[i+1][j] = dp[i][j]

            else:

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

    return dp[N][W]





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

lst = []

for i in range(n):

    w_, v_ =  list(map(int,input().split()))

    lst.append((w_, v_))

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

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

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

for i in range(n):

    wi, vi = wv[i]

    for j in range(w+1):

        if j<wi:

            dp[i+1][j] = dp[i][j]

        else:

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

            

print((dp[n][w]))
def knapsack_1(N, W, lst):
    # N : 品物数
    # W : 重みの総和
    # lst (wi,vi) : 商品iの重みwi、価値vi
    # dp[i][j] : i番目の品物から重さの総和がj以下になるように選んだ場合の価値の総和の最大値
    dp = [[0 for i in range(W + 1)] for _ in range(N + 1)]
    for i in range(N):
        for j in range(W + 1):
            if j < lst[i][0]:
                dp[i + 1][j] = dp[i][j]
            else:
                dp[i + 1][j] = max(dp[i][j], dp[i][j - lst[i][0]] + lst[i][1])
    return dp[N][W]


n, w = list(map(int, input().split()))
lst = []
for i in range(n):
    w_, v_ = list(map(int, input().split()))
    lst.append((w_, v_))
print((knapsack_1(n, w, lst)))

n, w = list(map(int, input().split()))
wv = [list(map(int, input().split())) for _ in range(n)]
dp = [[0] * (w + 1) for _ in range(n + 1)]
for i in range(n):
    wi, vi = wv[i]
    for j in range(w + 1):
        if j < wi:
            dp[i + 1][j] = dp[i][j]
        else:
            dp[i + 1][j] = max(dp[i][j], dp[i][j - wi] + vi)
print((dp[n][w]))

-def knapsack_1(N, W, lst): -    # N : 品物数 -    # W : 重みの総和 -    # lst (wi,vi) : 商品iの重みwi、価値vi -    # dp[i][j] : i番目の品物から重さの総和がj以下になるように選んだ場合の価値の総和の最大値 -    dp = [[0 for i in range(W + 1)] for _ in range(N + 1)] -    for i in range(N): -        for j in range(W + 1): -            if j < lst[i][0]: -                dp[i + 1][j] = dp[i][j] -            else: -                dp[i + 1][j] = max(dp[i][j], dp[i][j - lst[i][0]] + lst[i][1]) -    return dp[N][W] - - -lst = [] +wv = [list(map(int, input().split())) for _ in range(n)] +dp = [[0] * (w + 1) for _ in range(n + 1)] -    w_, v_ = list(map(int, input().split())) -    lst.append((w_, v_)) -print((knapsack_1(n, w, lst))) +    wi, vi = wv[i] +    for j in range(w + 1): +        if j < wi: +            dp[i + 1][j] = dp[i][j] +        else: +            dp[i + 1][j] = max(dp[i][j], dp[i][j - wi] + vi) +print((dp[n][w]))