{-# LANGUAGE FlexibleContexts #-}

import           Control.Arrow
import           Control.Monad
import           Data.Array
import qualified Data.ByteString       as BS
import qualified Data.ByteString.Char8 as BS8
import           Data.Function
import           Data.Int
import           Data.Maybe            as Maybe
import           Debug.Trace

getStrings :: IO [String]
getStrings = map BS8.unpack . BS8.words <$> BS.getLine

getChars :: IO String
getChars = getLine

getInts :: IO [Int]
getInts =
  (map (fst . Maybe.fromJust . BS8.readInt) . BS8.words) `fmap` BS.getLine

getInt64s :: IO [Int64]
getInt64s =
  (map (fromIntegral . fst . Maybe.fromJust . BS8.readInteger) . BS8.words) `fmap`
  BS.getLine

getArray :: IO [a] -> Int -> IO (Array Int a)
getArray f a = listArray (0, a - 1) <$> f

getArray2 :: IO [a] -> Int -> Int -> IO (Array (Int, Int) a)
getArray2 f a b = listArray ((0, 0), (a - 1, b - 1)) . concat <$> replicateM a f

solve :: Int -> Int -> Array Int (Int, Int) -> Int
solve n m arr = dp ! (n, m)
  where
    dp =
      array
        ((0, 0), (n, m))
        [((i, j), solve i j) | i <- [0 .. n], j <- [0 .. m]]
    solve i rem = max skip ambil
      where
        skip = solve' (i - 1) rem
        ambil = solve' (i - 1) (rem - fst (arr ! i)) + snd (arr ! i)
    solve' i rem
      | rem < 0 = minBound `div` 4
      | i == 0 = 0
      | otherwise = dp ! (i, rem)

main :: IO ()
main = do
  [n, m] <- getInts
  arr <-
    listArray (1, n) <$>
    replicateM
      n
      (do [a, b] <- getInts
          return (a, b))
  print $ solve n m arr
