import Control.Monad
import Control.Monad.State
import qualified Data.Map as M
import Data.Map ((!))
type Ints = M.Map Int Int
type Memo a b = M.Map a b
type DP a b = a -> State (Memo a b) b

main :: IO ()
main = do
    [n, c] <- (map read . words) <$> getLine
    wvs <- map readLine2 <$> replicateM n getLine
    print $ solve (n, c) wvs

-- |
--
-- >>> solve (4,6) [(2,1),(3,4),(4,10),(3,4)]
-- 11
solve :: (Int, Int) -> [(Int, Int)] -> Int
solve (n, c) wvs = rec (0, c)
  where
    (ws, vs) = toMap2 wvs

    rec :: (Int, Int) -> Int
    rec = evalDP rec'

    rec' :: DP (Int, Int) Int
    rec' = dp $ \ (i, j) ->
      if i >= n
        then return 0
        else do
          yes <- rec' (i + 1, j - (ws ! i))
          no <- rec' (i + 1, j)
          if ws ! i > j
            then return no
            else return $ max ((vs ! i ) + yes) no

-- DP
dp :: Ord a => DP a b -> DP a b
dp f x = do
  memo <- gets (M.lookup x)
  case memo of
       Just y  -> return y
       Nothing -> do
         y <- f x
         modify (M.insert x y)
         return y

evalDP :: DP a b -> a -> b
evalDP f x = evalState (f x) M.empty

-- Utility
toMap2 :: [(Int, Int)] -> (Ints, Ints)
toMap2 x2s = (x0map, x1map)
  where
    x0map = M.fromList $ zip ixs x0s
    x1map = M.fromList $ zip ixs x1s
    ixs = [0 .. (length x2s - 1)]
    (x0s, x1s) = unzip x2s

readLine2 :: String -> (Int,Int)
readLine2 = tuplify2 . map read . words
    where
      tuplify2 [] = (0, 0)
      tuplify2 [x] = (x, 0)
      tuplify2 (x:y:_) = (x, y)
