module Main where
import qualified Data.Vector as V
import Data.Vector (Vector)
import Data.Vector ((!))
import Data.Vector ((!?))
import Control.Applicative

main :: IO ()
main = do
  n:maxw:_ <- map read . words <$> getLine :: IO [Int]
  vws <- V.replicateM n $ do
    v:w:_ <- map read . words <$> getLine :: IO [Int]
    return (v,w)
  print $ V.maximum $ solve vws (maxw+1)
  return ()

solve :: Vector (Int,Int) -> Int -> Vector Int
solve vws maxw = V.foldl' next v0 vws
  where
    v0 :: Vector Int
    v0 = V.replicate (maxw) 0
    next :: Vector Int -> (Int,Int) -> Vector Int
    --next vs _ | traceShow vs False = undefined
    next vs (v,w) = V.generate maxw gen
      where
        gen i = max v1 v2
          where
            v1 = vs ! i
            v2 = case vs !? (i - w) of
              Nothing -> 0
              Just p -> p + v