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<<30)+w}
I = {}
tv=tw = 0
I[1<<60] = WV.each_with_index.count {|(w,v),i| break i if w>W; I[v]||=i; tv+=v; tw+=w}
K = I.keys
A = Array.new(tv+1, [tw,(1<<I[K[-1]])-1])
A[0] = [0,0]
GC.start
GC.disable
l = tw > W ? 0 : tv
l.upto(tv) {|n|
  c,b = A[n]
  l = n if c <= W
  next  if c >= W
  K.each_cons(2) {|v,w|
    i,j = I[v],I[w]
    next  if b[j-1] > 0
    x = b | b+(1<<i)
    i += 1  while b[i] > 0
    w = c + WV[i][0]
    A[v+n] = [w,x]  if A[v+n][0] > w
  }
}
p l