WV = $<.read.split.map(&:to_i).each_slice(2).to_a
N,W = WV.shift
WV.sort_by! {|w,v| w>W ? [1<<60] : [v,-w]}
I = {}
tv=tw = 0
WV.each_with_index {|(w,v),i| break I[0]=i if w>W; tv+=v; tw+=w; I[v] ||= i}
I[0] ||= N
K = I.keys
A = Array.new(tv+1)
A[tv] = [tw,0]
tv.downto(0) {|n|
  c,b = A[n]
  next  if !c
  exit(p(n)&&0)  if c <= W
  K.each_cons(2) {|v,x|
    i,j = I[v],I[x]
    m = 1 << j
    next  if m <= (b&(m-1))+(1<<i)
	i += 1  while b[i] > 0
    w = c - WV[i][0]
    v = n - v
    A[v] = [w,b+(1<<i)]  if (A[v]||[tw])[0] > w
  }
}