{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE RankNTypes #-}
{-# LANGUAGE ScopedTypeVariables #-}
import Control.Monad
import Control.Monad.ST
import Data.Array
import qualified Data.Array.Unboxed as UA
import Data.Array.ST
import Data.Array.MArray
import Data.Bool

solve :: Int -> [(Int, Int)] -> Int -> Int
solve n goods w = mf (0, w) where
  mf = memoize ((0,0), (n, w)) f
  gdary = listArray (0, n-1) goods
  f mf (i, j)
    | i == n = return 0
    | j < wi = mf (i+1, j)
    | otherwise = liftM2 max (mf (i+1, j)) ((+vi) <$> mf (i+1, j-wi)) 
    where (wi, vi) = gdary ! i

memoize :: forall i a . (Ix i, UA.IArray UA.UArray a) => (i, i) ->
  (forall m . Monad m => (i -> m a) -> i -> m a) -> i -> a
memoize ran fun i
  | memd UA.! i = memo UA.! i
  | otherwise = error "Not written!"
  where
    memo :: UA.UArray i a
    memd :: UA.UArray i Bool
    (memo, memd) =  runST $ do
      memo <- newArray_ ran
      memd <- newArray ran False
      forM_ (range ran) $ calc (memo, memd)
      memo <- freeze memo
      memd <- freeze memd
      return (memo, memd)
    calc :: forall s .
      (STArray s i a, STArray s i Bool) -> i -> ST s a
    calc (memo, memd) i = bool res mem =<< readArray memd i where
        mem = readArray memo i
        res = do
          rs <- fun (calc (memo, memd)) i
          writeArray memo i rs
          writeArray memd i True
          return rs

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