{-# LANGUAGE BangPatterns #-}
import Control.Arrow
import Control.Monad.Fix
import Data.Foldable
import qualified Data.Vector.Unboxed as VU
import qualified Data.Vector.Unboxed.Mutable as VUM
import qualified Data.ByteString.Char8 as B
import Data.ByteString.Internal (accursedUnutterablePerformIO)
import qualified Data.Set as S
import System.IO.Unsafe
import Debug.Trace

unew :: VU.Unbox a => Int -> VUM.IOVector a
unew !n = accursedUnutterablePerformIO $ VUM.unsafeNew n

uread :: VU.Unbox a => Int -> VUM.IOVector a -> a
uread !i !v = accursedUnutterablePerformIO $ VUM.unsafeRead v i

uwrite :: VU.Unbox a => Int -> a -> VUM.IOVector a -> VUM.IOVector a
uwrite !i !a !v =
  accursedUnutterablePerformIO $ VUM.unsafeWrite v i a >> return v

umodify :: VU.Unbox a => Int -> (a -> a) -> VUM.IOVector a -> VUM.IOVector a
umodify !i !f !v =
  accursedUnutterablePerformIO $ VUM.unsafeModify v f i >> return v

uthaw :: VU.Unbox a => VU.Vector a -> VUM.IOVector a
uthaw !v = accursedUnutterablePerformIO $ VU.unsafeThaw v

ufreeze :: VU.Unbox a => VUM.IOVector a -> VU.Vector a
ufreeze !v = accursedUnutterablePerformIO $ VU.unsafeFreeze v

solve :: Int -> Int -> VU.Vector (Int, Int) -> Int
solve !n !w !wvs = uread (toIndex n w) dp
 where
  toIndex i k = i * (w + 1) + k

  dp = VU.ifoldl'
    ( \(!dp) !i (!wi, !vi) -> foldl'
      ( \(!dp) !k ->
        let z = max
              (uread (toIndex i k) dp)
              (if k - wi < 0 then 0 else uread (toIndex i (k - wi)) dp + vi)
        in  z `seq` uwrite (toIndex (i + 1) k) z dp
      )
      dp
      [0 .. w]
    )
    ( foldl' (\(!dp) !k -> uwrite (toIndex 0 k) 0 dp)
             (unew (succ n * succ w))
             [0 .. w]
    )
    wvs

main = do
  let readInt = fmap (second B.tail) . B.readInt

  (n, w) <-
    (\vec -> (vec VU.! 0, vec VU.! 1)) . VU.unfoldrN 2 readInt <$> B.getLine
  wvs <-
    VU.replicateM n
    $   (\vec -> (vec VU.! 0, vec VU.! 1))
    .   VU.unfoldrN 2 readInt
    <$> B.getLine
  print $ solve n w wvs
