{-# LANGUAGE NumDecimals #-}
module Main (main) where
import Control.Applicative
import Control.Monad
import Data.Maybe
import qualified Data.Vector.Unboxed as U
import qualified Data.Vector.Unboxed.Mutable as UM
getInts :: IO [Int]
getInts = map read . words <$> getLine

main :: IO ()
main = do
  n:w:_ <- getInts
  xs <- U.replicateM n $ do
    v:w:_ <- getInts
    return (v,w)
  print $ solve1 w xs

solve1 :: Int -> U.Vector (Int,Int) -> Int
solve1 w xs = U.maximum . U.foldl' step (U.replicate (w+1) 0) $
  xs
  where
    step maxs (val,weight) = U.generate (w+1) $
      \maxWeight -> (maxs U.! maxWeight)
                    `max` (val + (fromMaybe (-1e10) $ maxs U.!? (maxWeight - weight)))