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

main = do
  [n,maxW] <- unfoldr (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine
  items <- U.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 -> U.Vector (Int, Int64) -> U.Vector Int64
solve maxW xs
  | U.null xs = U.replicate (maxW + 1) 0
  | otherwise = let (w,v) = U.head xs
                    a = solve maxW (U.tail xs)
                in U.generate (maxW + 1)
                   $ \i -> if w <= i
                           then max (a U.! i) (a U.! (i - w) + v)
                           else a U.! i
