import Data.Array
--最初のアレイは、重み、価値の順。
create_tab::Int -> Int -> Array Int (Int,Int) -> Array (Int,Int) Int
create_tab n w ar = listArray ((0,0),(n,w)) [if i==0 then 0 else (max ((create_tab n w ar)!(i-1,k)) (if k>= fst(ar!i) then ((create_tab n w ar)!(i-1,k - (fst(ar!i))))+(snd(ar!i)) else 0))  | i<-[0..n],k<-[0..w]]

solver::Int-> Int-> Array Int (Int,Int) -> Int
solver n w ar = (create_tab n w ar)!(n,w)

getter::Int -> IO [(Int,Int)]
getter 0 = return []
getter n = do
  wvc<-getLine
  let w:v:[]=map read (words wvc)::[Int]
  rest<-getter (n-1)
  return ((w,v):rest)

main::IO()
main=do
  nwc<-getLine
  let n:w:[]=map read (words nwc)::[Int]
  dat<-getter n
  let ar = listArray (1,n) dat
  print (solver n w ar) 