N, W = gets.chomp.split.map(&:to_i)
wn = {}
N.times do |i|
  wn[i] = gets.chomp.split.map(&:to_i)
end

def max(a, b)
  a > b ? a : b
end

dp = Hash.new { |k,h| k[h] = {} }
0.upto(N-1) do |i|
  0.upto(W) do |w|
    dp[i+1][w] = max(dp[i+1][w].to_i, dp[i][w].to_i)
    dp[i+1][w] = max(dp[i+1][w].to_i, dp[i][w - wn[i].first].to_i + wn[i].last) if w >= wn[i].first
  end
end

print dp.values.map {|d| d.values.max }.compact.max