import Control.Monad
import Data.List
import qualified Data.ByteString.Char8 as B
import Data.Array

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

    print $ f n w wvs

f n w wvs = dp ! (n,w)
    where
    dp = array ((0,0),(n,w)) $ map (\j->((0,j),0)) [0..w] ++ map proc [(i,wi,vi,j)|(i,[wi,vi])<-zip [1..] wvs,j<-[0..w]]
    proc (i,wi,vi,j)|j<wi= ((i,j), dp ! (i-1,j)) |j>=wi= ((i,j), max (dp ! (i-1,j)) (vi + dp ! (i-1,j-wi)))