{-# 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 = trace (show (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)

solve :: Int -> Int -> [(Int, Int)] -> Int
solve n m arr = maximum . elems $ res
  where
    res = foldl trans (listArray (0, m) (replicate (m + 1) 0)) arr
    trans memo (w, val) = listArray (0, m) [solve i | i <- [0..m]]
      where
        solve i = max pick skip
          where
            pick = if w <= i then (memo ! (i - w)) + val else minBound
            skip = memo ! i

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