$N,$W= gets.split.map(&:to_i)
$w_ary = []
$v_ary = []
$N.times do |n|
  w,v = gets.split.map(&:to_i)
  $w_ary << w
  $v_ary << v
end

$cache = {}
def calc(n, left)
  total = 0
  return 0 if n == $N

  key = "#{n}_#{left}"
  return $cache[key] unless $cache[key].nil?

  if $w_ary[n] <= left
    tmp1 = calc(n+1, left)
    tmp2 = calc(n+1, left - $w_ary[n]) + $v_ary[n]
    total = [tmp1,tmp2].max
  else
    total = calc(n+1, left)
  end
  $cache[key] = total
  total
end

total = calc(0, $W)
puts total
