local n,m=io.read("n","n")
local w,v={},{}
for i=1,n do
    w[i],v[i]=io.read("n","n")
end

local dp={}
for i=1,n+1 do
    dp[i]={}
    for j=0,m do
        dp[i][j]=0
    end
end

for i=1,n do
    for j=0,m do
        if j-w[i]>=0 then
            dp[i+1][j]=math.max(dp[i+1][j],dp[i][j-w[i]]+v[i])
        end
        dp[i+1][j]=math.max(dp[i+1][j],dp[i][j])
    end
end

print(string.format("%d",dp[n+1][m]))