import Data.Array
import Data.Array.IO
import Data.IORef

write_tab::Int -> Int ->IORef (Array Int (Int,Int)) ->  IORef (IOArray (Int,Int) (Maybe Int)) ->IO()
write_tab n w ar_ptr tab_ptr = do
  ref<-readIORef ar_ptr
  tab<-readIORef tab_ptr
  if n == 0 then do writeArray tab (n,w) (Just 0)
            else if fst(ref!n) <= w then do use_case<-readArray tab (n-1,w-(fst(ref!n)))
                                            not_use <-readArray tab (n-1,w)
                                            case (use_case,not_use) of
                                              (Just a,Just  b) ->do writeArray tab (n,w) (Just(max (a+snd(ref!n)) b))
                                              (Nothing,Just b) ->do write_tab (n-1) (w-(fst(ref!n))) ar_ptr tab_ptr
                                                                    use_case'<-readArray tab (n-1,w-(fst(ref!n)))
                                                                    let Just a = use_case'
                                                                    writeArray tab (n,w) (Just(max (a+snd(ref!n)) b))
                                              (Just a,Nothing )->do write_tab (n-1) w ar_ptr tab_ptr
                                                                    not_use'<-readArray tab (n-1,w)
                                                                    let Just b = not_use'
                                                                    writeArray tab (n,w) (Just(max (a+snd(ref!n)) b))
                                              (Nothing,Nothing)->do write_tab (n-1) (w-(fst(ref!n))) ar_ptr tab_ptr
                                                                    write_tab (n-1) w ar_ptr tab_ptr
                                                                    use_case'<-readArray tab (n-1,w-(fst(ref!n)))
                                                                    not_use' <-readArray tab (n-1,w)
                                                                    let Just a = use_case'
                                                                    let Just b = not_use'
                                                                    writeArray tab (n,w) (Just(max (a+snd(ref!n)) b))
                                    else do not_use <-readArray tab (n-1,w)
                                            case not_use of
                                              Nothing -> do write_tab (n-1) w ar_ptr tab_ptr
                                                            not_use'<-readArray tab (n-1,w)
                                                            let Just b = not_use'
                                                            writeArray tab (n,w) (Just b)
                                              Just b  -> do writeArray tab (n,w) (Just b)

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 ref = listArray (1,n) dat
  ar<-newArray ((0,0),(n,w)) Nothing
  ref_ptr<-newIORef ref
  tab_ptr<-newIORef ar
  write_tab n w ref_ptr tab_ptr
  ans<-readArray ar (n,w)
  let Just ans' = ans
  print ans'