import Data.Array
import Data.Array.ST
import Data.Array.MArray
import Control.Monad
import Control.Monad.ST

solve n goods w = runST $ do
  dp <- newArray ((0,0), (n,w)) (-1)
  f dp 0 w where
    gary = listArray (0, n-1) goods
    f :: STUArray s (Int,Int) Int -> Int -> Int -> ST s Int
    f dp i j = do
      mem <- readArray dp (i, j)
      if mem /= -1 then
        return mem
      else do
        res <- res
        writeArray dp (i, j) res
        return res
      where
        (wi, vi) = gary ! i
        res
          | i == n = return 0
          | j < wi = nxt
          | otherwise = liftM2 max nxt nx'
          where
            nxt = f dp (i+1) j
            nx' = (+vi) <$> f dp (i+1) (j-wi)

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