#参考 #4023546 by kamina_zzz
N,W = gets.split.map &:to_i
D = [[0,0]]
m = 0
N.times {
  w,v = gets.split.map &:to_i
  next if w+m > W
  D.push *D.inject([]) {|a,d|
    d[0]+w > W ? a : a << [d[0]+w, d[1]-v]
  }
  D.sort!.uniq! {|d| d[0]}
  m = D[0][0]  if m < D[0][0]
}
p -D.inject(0) {|m,(w,v)| m>v ? v : m}