import Control.Monad.State
import qualified Data.Map as Map
import qualified Data.Maybe
import Control.Applicative

type Index = (Int, Int)
type Value = Int
type Weight = Int
type Item = (Value, Weight)
type Knapsack = Map.Map Index Int


main :: IO ()
main = do
  [n, w] <- getInts
  ns <- replicateM n $ do
    [v, w'] <- getInts
    return (v, w')
--  printKnapsack n w ns
  print $ solve ns w n
getInts :: IO [Int]
getInts = map read . words <$> getLine

printKnapsack n w is = do
  let memo = evalState (dp (1, 1) is) (n, w, initMemo)
  let memo' = zip indexes $ map (`Map.lookup` memo) indexes
  mapM_ print memo'
  where
    indexes = do
      i <- [0..n]
      j <- [0..w]
      return (i, j)
    initMemo = Map.fromList $ zip indexes $ replicate (length indexes) 0

solve :: [Item] -> Int -> Int -> Int
solve is w n = mapMax n w $
               evalState (dp (1, 1) is) (n, w, initMemo)
  where
    initMemo = Map.fromList $ zip indexes (replicate (length indexes) 0) 
      where
        indexes = do
          i <- [0..n]
          j <- [0..w]
          return (i, j)
          
mapMax :: Int -> Int -> Knapsack -> Int
mapMax n w m = maximum $
             map (Data.Maybe.fromMaybe (-1) . (`Map.lookup` m)) $
             zip (replicate w n) [1..w]

dp :: Index -> [Item] -> State (Int, Int,  Knapsack) Knapsack
dp _ [] = do
  (_, _, memo) <- get
  return memo
dp (i, j) as@((vi, wi):rs) = do
  (n, w, memo) <- get
  case j of
    _ | j > w -> dp (i+1, 0) rs
    _ | j < wi -> do
       let v = Map.lookup (i-1, j) memo
       case v of
         Nothing -> do
           modify (modifyMemo (i, j) 0)
           dp (i, j+1) as
         Just y -> do
           modify (modifyMemo (i, j) y)
           dp (i, j+1) as
    _ -> do
      let v = Map.lookup (i-1, j-wi) memo
      case v of
        Nothing -> do
          modify (modifyMemo (i, j) 0)
          dp (i, j+1) as
        Just y -> do
          let v' = Data.Maybe.fromMaybe (-1) $ Map.lookup (i-1, j) memo 
          modify (modifyMemo (i, j) (max (y+vi) v'))
          dp (i, j+1) as

modifyMemo :: Index -> Value -> (Int, Int, Knapsack) -> (Int, Int, Knapsack)
modifyMemo pos val (n, w, memo) =
  (n, w, Map.insert pos val memo)