n, W = gets.chomp.split.map(&:to_i)

dp = Array.new(W+1,0)
w = []
v = []
n.times do |i|
  ww, vv = gets.chomp.split.map(&:to_i)
  w.push ww
  v.push vv
end

n.times do |i|
  W.downto(0).each do |weight|
    if w[i] <= weight
      dp[weight] = dp[weight-w[i]] + v[i] if dp[weight] < dp[weight-w[i]] + v[i]
    end
  end
end

# dp.each{|line| p line}
# p dp
puts dp[W]

