import Control.Monad
import Data.List
import qualified Data.ByteString.Char8 as B
import qualified Data.Vector.Unboxed as UV

r2 [a,b]=(a,b)
main = do
    [n,w]<-map read.words<$>getLine::IO [Int]
    wvs<-replicateM n $ r2.unfoldr (B.readInt.B.dropWhile(<'!'))<$>B.getLine
    print $ f n w wvs

f n w = (UV.! w).foldl' p (UV.replicate (w+1) 0) where
    p v0 (wi,vi) = UV.zipWith max v0 (UV.replicate wi 0 UV.++ UV.map (+vi) v0)