{-# LANGUAGE RankNTypes #-}
import qualified Data.Ix as I
import qualified Data.Vector.Unboxed as U
import qualified Data.Vector.Unboxed.Mutable as UM
import Control.Monad
import Control.Monad.ST

solve :: Int -> [(Int,Int)] -> Int -> Int
solve n goods' w = f (0, w) where
  goods = U.fromList goods'
  f = memoize ((0,0), (n,w)) [(0,w)] f'
  f' f (i, j)
    | i == n = return 0
    | j < wi = nxt
    | otherwise = liftM2 max nxt nx'
    where
      nxt = f (i+1, j)
      nx' = (+vi) <$> f (i+1, j-wi)
      (wi, vi) = goods U.! i

--{ memoize
memoize :: (I.Ix i, U.Unbox e) => (i, i) -> [i] ->
  (forall m. Monad m => (i -> m e) -> i -> m e) -> (i -> e)
memoize ran is fun i = U.unsafeIndex memo ix
  where
    ix = I.index ran i
    size = I.rangeSize ran
    memo = runST $ do
      memo <- UM.unsafeNew size
      memd <- UM.replicate size False
      forM_ is $ calc memo memd
      U.unsafeFreeze memo
    calc memo memd i = do
      written <- UM.unsafeRead memd ix
      unless written $ do
        UM.unsafeWrite memo ix =<< fun (calc memo memd) i
        UM.unsafeWrite memd ix True
      UM.unsafeRead memo ix
      where ix = I.index ran i
--}

main = do
  [n,w] <- map read.words <$> getLine
  goods <- replicateM n $ (\[a,b]->(a,b)).map read.words <$> getLine
  print $ solve n goods w