
n,wmax=gets.split.map(&:to_i)
dp=Array.new(110){[0]*10010}
for i in 0..n-1
    vi,wi=gets.split.map(&:to_i)
    for w  in 1..wmax
    if (w-wi)>=0
    dp[i+1][w]=[dp[i][w-wi]+vi,dp[i][w]].max
    else
    dp[i+1][w]=dp[i][w]
    end
    end
end
#p dp[0..10]
p dp[n][wmax]
