n, w = STDIN.readline.strip.split(' ').map(&:to_i)
wv = STDIN.read.split("\n").map{|l| l.split(' ').map(&:to_i)}

def opt(w, i, wv, m)
  return 0 if i == -1
  return m[i][w] if m[i][w]
  if wv[i][0] <= w
    with = wv[i][1] + opt(w-wv[i][0], i-1, wv, m)
    without = opt(w, i-1, wv, m)
    m[i][w] = [with, without].max
  else 
    m[i][w] = opt(w, i-1, wv, m)
  end
end

m = Array.new(wv.size){[]}
puts opt(w, wv.size-1, wv, m)
