import Control.Monad
import Data.Maybe
import qualified Data.ByteString.Char8 as BS
import Data.List
import qualified Data.Vector.Unboxed as VU
import qualified Data.Vector.Unboxed.Mutable as VUM

readInt = fst . fromJust . BS.readInt
readIntList = map readInt . BS.words
getInt = readInt <$> BS.getLine
getIntList = readIntList <$> BS.getLine

main = do
    [n,maxW] <- getIntList
    items <- replicateM n $ do
        [w,v] <- getIntList
        return (w,v)
    print $ (solve maxW items) VU.! maxW


solve maxW [] = VU.replicate (maxW+1) 0
solve maxW ((w,v):xs) 
  = let a = solve maxW xs 
    in VU.generate (maxW+1)
      $ \i -> if w <= i then
                  max (a VU.! i) (a VU.! (i-w) + v)
              else a VU.! i