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

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

#重さ、価値の順

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

#配列のインデックスを重さに対応させる

 

for i in range(n):

    for sum_w in range(w+1):

        

        if sum_w-l[i][0]>=0:

            dp[i+1][sum_w]=max(dp[i+1][sum_w],dp[i][sum_w-l[i][0]]+l[i][1])

        #l[i]を入れるとき

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

        #入れない時

print((dp[-1][-1]))

#DP-C



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

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



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



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

    for sum_w in range(w+1):

        if sum_w-l[i-1][0]>=0:

            dp[i][sum_w]=max(dp[i-1][sum_w],dp[i-1][sum_w-l[i-1][0]]+l[i-1][1])

        else:

            dp[i][sum_w]=dp[i-1][sum_w]



print((max(dp[-1])))
n, w = list(map(int, input().split()))
l = [list(map(int, input().split())) for i in range(n)]
# 重さ、価値の順
dp = [[0] * (w + 1) for i in range(n + 1)]
# 配列のインデックスを重さに対応させる
for i in range(n):
    for sum_w in range(w + 1):
        if sum_w - l[i][0] >= 0:
            dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w - l[i][0]] + l[i][1])
        # l[i]を入れるとき
        dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w])
        # 入れない時
print((dp[-1][-1]))

# DP-C
n, w = list(map(int, input().split()))
l = [list(map(int, input().split())) for i in range(n)]
dp = [[0] * (w + 1) for i in range(n + 1)]
for i in range(1, n + 1):
    for sum_w in range(w + 1):
        if sum_w - l[i - 1][0] >= 0:
            dp[i][sum_w] = max(
                dp[i - 1][sum_w], dp[i - 1][sum_w - l[i - 1][0]] + l[i - 1][1]
            )
        else:
            dp[i][sum_w] = dp[i - 1][sum_w]
print((max(dp[-1])))

+# DP-C -# 重さ、価値の順 -# 配列のインデックスを重さに対応させる -for i in range(n): +for i in range(1, n + 1): -        if sum_w - l[i][0] >= 0: -            dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w - l[i][0]] + l[i][1]) -        # l[i]を入れるとき -        dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w]) -        # 入れない時 -print((dp[-1][-1])) +        if sum_w - l[i - 1][0] >= 0: +            dp[i][sum_w] = max( +                dp[i - 1][sum_w], dp[i - 1][sum_w - l[i - 1][0]] + l[i - 1][1] +            ) +        else: +            dp[i][sum_w] = dp[i - 1][sum_w] +print((max(dp[-1])))