(n,w),*wv=$<.map{|l|l.split.map(&:to_i)}

def dfs(w,wv,weight,value,idx)
  if wv[idx]
    [
      dfs(w,wv,weight,           value,           idx+1),
      dfs(w,wv,weight+wv[idx][0],value+wv[idx][1],idx+1)
    ].max
  else
    w<weight ? 0 : value
  end
end

p dfs(w,wv,0,0,0)
