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

solve :: Int -> [(Int,Int)] -> Int -> Int
solve n goods w = runST $ do
  dp <- newArray ((0,0), (n,w)) (-1)
  f dp 0 w
  where
    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 <- if i == n then
          return 0
        else if j < wi then
          f dp (i+1) j
        else
          liftM2 max (f dp (i+1) j) ((+vi) <$> f dp (i+1) (j-wi))
        writeArray dp (i, j) res
        return res
      where (wi, vi) = gary ! i
    gary = listArray (0, n-1) goods

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