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

dp = {0=>0}

wv.each{|wi,vi|
  add={}
  dp.each{|val,wei|
    if (neww = wi+wei) <= w
      add[val+vi] = [dp[val+vi]||INF,neww].min
    end
  }
  dp.update(add)
}

p dp.keys.max