import           Control.Monad
import           Data.Array.IArray

main = do
    [n,w] <- map read . words <$> getLine :: IO [Int]
    wv <- replicateM n $
        (\[a,b] -> (a,b)) . map read . words <$> getLine :: IO [(Int, Int)]
    print $ knapsack w wv

knapsack :: Int -> [(Int,Int)] -> Int
knapsack c wv = memo!(n,c)
  where
    n = length wv
    k = ((0,0),(n,c))
    memo = listArray k [f t | t <- range k] :: Array (Int,Int) Int
    f (i,ci)
      | i == 0 || ci == 0 = 0
      | wi > ci = memo!(i-1, ci)
      | otherwise = maximum [vi + memo!(i-1, ci-wi), memo!(i-1, ci)]
      where
        wv' = listArray (1, n) wv :: Array Int (Int, Int)
        wi = fst (wv'!i)
        vi = snd (wv'!i)