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

w=[0]*n

v=[0]*n

for i in range(n):

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

dp=[0]*(W+1)

for i in range(n):

    j=W

    while j>=w[i]:

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

        j-=1



print((dp[W]))
"""

【01ナップザック問題】

重さと価値がそれぞれw_i,v_iであるようなn個の品物がある.

これらの品物の中から, 重さの総和がWを超えないように選んだ時の,

価値の総和の最大値を求めよ.

1<=n<=100, 1<=w_i,v_i<=100, 1<=W<=10000

"""

#------------------------------------------------------------------------------



#入力,準備

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

w=[0]*n

v=[0]*n

for i in range(n):

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

dp=[0]*(W+1)



#メイン

#dp[j] : 重さの総和がjを超えないように選んだ時の価値の総和の最大値

for i in range(n):

    j=W

    while j>=w[i]:

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

        j-=1



print((dp[W]))
n, W = list(map(int, input().split()))
w = [0] * n
v = [0] * n
for i in range(n):
    w[i], v[i] = list(map(int, input().split()))
dp = [0] * (W + 1)
for i in range(n):
    j = W
    while j >= w[i]:
        dp[j] = max(dp[j], dp[j - w[i]] + v[i])
        j -= 1
print((dp[W]))

"""
【01ナップザック問題】
重さと価値がそれぞれw_i,v_iであるようなn個の品物がある.
これらの品物の中から, 重さの総和がWを超えないように選んだ時の,
価値の総和の最大値を求めよ.
1<=n<=100, 1<=w_i,v_i<=100, 1<=W<=10000
"""
# ------------------------------------------------------------------------------
# 入力,準備
n, W = list(map(int, input().split()))
w = [0] * n
v = [0] * n
for i in range(n):
    w[i], v[i] = list(map(int, input().split()))
dp = [0] * (W + 1)
# メイン
# dp[j] : 重さの総和がjを超えないように選んだ時の価値の総和の最大値
for i in range(n):
    j = W
    while j >= w[i]:
        dp[j] = max(dp[j], dp[j - w[i]] + v[i])
        j -= 1
print((dp[W]))

+""" +【01ナップザック問題】 +重さと価値がそれぞれw_i,v_iであるようなn個の品物がある. +これらの品物の中から, 重さの総和がWを超えないように選んだ時の, +価値の総和の最大値を求めよ. +1<=n<=100, 1<=w_i,v_i<=100, 1<=W<=10000 +""" +# 入力,準備 +# メイン +# dp[j] : 重さの総和がjを超えないように選んだ時の価値の総和の最大値