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

w, v = [0] * N, [0] * N

for i in range(N):

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



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

# dp[i][j](j=0,1,...,W)の値が求まっている状態で、dp[i+1][j]を更新することを考える



for i in range(N):

    for j in range(W+1):#重さ0からWまでチェック

        if j-w[i]>=0:#入れてもOKな場合,容量と価値を足す

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

        else:#何も入れずに先に進む

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

print((max(dp[N])))

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

w, v = [0] * N, [0] * N

for i in range(N):

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



DP = [[0] * (W + 2) for i in range(N + 2)]

"""

DP[0][W]

DP[i][j]

i:荷物の個数

j:残り容量

"""

for i in range(N):

    for j in range(W+1):

        if j>=w[i]:#残り容量に余裕があるとき

            DP[i+1][j]=max(DP[i][j],DP[i][j-w[i]]+v[i])

        else:

            DP[i+1][j]=DP[i][j]



print((max(DP[N])))
N, W = list(map(int, input().split()))
w, v = [0] * N, [0] * N
for i in range(N):
    w[i], v[i] = list(map(int, input().split()))
dp = [[0] * (W + 1) for _ in range(N + 1)]
# dp[i][j](j=0,1,...,W)の値が求まっている状態で、dp[i+1][j]を更新することを考える
for i in range(N):
    for j in range(W + 1):  # 重さ0からWまでチェック
        if j - w[i] >= 0:  # 入れてもOKな場合,容量と価値を足す
            dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i])
        else:  # 何も入れずに先に進む
            dp[i + 1][j] = dp[i][j]
print((max(dp[N])))

N, W = list(map(int, input().split()))
w, v = [0] * N, [0] * N
for i in range(N):
    w[i], v[i] = list(map(int, input().split()))
DP = [[0] * (W + 2) for i in range(N + 2)]
"""
DP[0][W]
DP[i][j]
i:荷物の個数
j:残り容量
"""
for i in range(N):
    for j in range(W + 1):
        if j >= w[i]:  # 残り容量に余裕があるとき
            DP[i + 1][j] = max(DP[i][j], DP[i][j - w[i]] + v[i])
        else:
            DP[i + 1][j] = DP[i][j]
print((max(DP[N])))

-dp = [[0] * (W + 1) for _ in range(N + 1)] -# dp[i][j](j=0,1,...,W)の値が求まっている状態で、dp[i+1][j]を更新することを考える +DP = [[0] * (W + 2) for i in range(N + 2)] +""" +DP[0][W] +DP[i][j] +i:荷物の個数 +j:残り容量 +""" -    for j in range(W + 1):  # 重さ0からWまでチェック -        if j - w[i] >= 0:  # 入れてもOKな場合,容量と価値を足す -            dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i]) -        else:  # 何も入れずに先に進む -            dp[i + 1][j] = dp[i][j] -print((max(dp[N]))) +    for j in range(W + 1): +        if j >= w[i]:  # 残り容量に余裕があるとき +            DP[i + 1][j] = max(DP[i][j], DP[i][j - w[i]] + v[i]) +        else: +            DP[i + 1][j] = DP[i][j] +print((max(DP[N])))