import Data.Char (isSpace)
import Data.Int (Int64)
import Data.List (unfoldr)
import qualified Data.Vector.Unboxed as U
import qualified Data.ByteString.Char8 as BS
import Control.Monad (replicateM)

main = do
  [n,maxW] <- unfoldr (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine
  items <- replicateM n $ do
    [w,v] <- unfoldr (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine
    return (w, fromIntegral v :: Int64)
  print $ solve maxW items U.! maxW

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