{-# OPTIONS_GHC -O2 #-}
import Control.Applicative
import Data.IORef
import qualified Data.Vector.Mutable as VM
import Control.Monad

main = do
  [_,capa] <- map (read :: String -> Int) . words <$> getLine
  goods <- map (map (read :: String -> Int) . words) . lines <$> getContents
  capaVM <- VM.replicate (capa+1) 0
  ans <- newIORef 0
  mapM_ (resolve capa capaVM ans) goods
  print =<< readIORef ans

resolve capa capaVM ans [v,w] =
  if capa < w
    then return ()
    else mapM_ (koushin [v,w]) (reverse [0..(capa-w)])
       where
         koushin [v,w] n = do
           oldValue <- VM.read capaVM n
           newValue <- VM.read capaVM (n+w)
           judge oldValue newValue
             where
               judge oldValue newValue
                 | n == 0 && newValue <= v  = kakikae
                 | n ==0                    = return ()
                 | newValue >= v + oldValue = return ()
                 | otherwise  = kakikae
                 where
                   kakikae = do
                     VM.write capaVM (n+w) (v + oldValue)
                     ans' <- readIORef ans
                     writeIORef ans (max ans' (v + oldValue))