n, w = gets.split.map(&:to_i)
wv = []
n.times do
  wv << gets.split.map(&:to_i)
end
wv.sort_by! { |y| y[0] }
dp = Array.new(w+1, 0)
wv.each do |tw, tv|
  w.downto(tw).each do |cw|
    dp[cw] = dp[cw-tw] + tv if dp[cw] < dp[cw-tw] + tv
  end
end
puts dp.last