import Data.Vector ((!), generate, fromList)
import Control.Monad

solve n goods w = f 0 w where
  f = memo2 f' (n+1) (w+1)
  f' i j
    | i == n = 0
    | j < vi = f (i+1) j
    | otherwise = max (f (i+1) j) (f (i+1) (j-wi) + vi)
    where (wi, vi) = g ! i
  g = fromList goods

memo2 f' n m i j = (generate n (generate m . f') ! i) ! j

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