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

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

 

dp = [-1 for _ in range(W + 1)] # dp[重量の総和]:= 価値の総和

dp[0] = 0

 

for i in range(N):

  w, v = wv[i]

  for j in range(W, -1, -1):

    if dp[j] >= 0 and j + w <=  W:

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

      

print((max(dp)))
# 埋める配列

# dp[w] : 入っている重さがwのときの価値の最大値



# 計算方法

# dp[0][0] = 0

# dp[w] = max(dp[w - wi] + vi)



# 埋める順序

# 後ろから



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

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



dp = [0] * (W + 1)

for i in range(N):

    wi, vi = wv[i]

    for j in range(W, -1, -1):

        if j - wi >= 0:

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

            

print((dp[-1]))
N, W = list(map(int, input().split()))
wv = [list(map(int, input().split())) for _ in range(N)]
dp = [-1 for _ in range(W + 1)]  # dp[重量の総和]:= 価値の総和
dp[0] = 0
for i in range(N):
    w, v = wv[i]
    for j in range(W, -1, -1):
        if dp[j] >= 0 and j + w <= W:
            dp[j + w] = max(dp[j + w], dp[j] + v)
print((max(dp)))

# 埋める配列
# dp[w] : 入っている重さがwのときの価値の最大値
# 計算方法
# dp[0][0] = 0
# dp[w] = max(dp[w - wi] + vi)
# 埋める順序
# 後ろから
N, W = list(map(int, input().split()))
wv = [list(map(int, input().split())) for _ in range(N)]
dp = [0] * (W + 1)
for i in range(N):
    wi, vi = wv[i]
    for j in range(W, -1, -1):
        if j - wi >= 0:
            dp[j] = max(dp[j], dp[j - wi] + vi)
print((dp[-1]))

+# 埋める配列 +# dp[w] : 入っている重さがwのときの価値の最大値 +# 計算方法 +# dp[0][0] = 0 +# dp[w] = max(dp[w - wi] + vi) +# 埋める順序 +# 後ろから -dp = [-1 for _ in range(W + 1)]  # dp[重量の総和]:= 価値の総和 -dp[0] = 0 +dp = [0] * (W + 1) -    w, v = wv[i] +    wi, vi = wv[i] -        if dp[j] >= 0 and j + w <= W: -            dp[j + w] = max(dp[j + w], dp[j] + v) -print((max(dp))) +        if j - wi >= 0: +            dp[j] = max(dp[j], dp[j - wi] + vi) +print((dp[-1]))