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

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 = runST $ do
    dp <- newArray ((0,0),(n,100000)) maxBound :: ST s (STUArray s (Int,Int) Int)
    writeArray dp (0,0) 0
    forM_ [(i,wi,vi,j)|(i,[wi,vi])<-zip [1..] wvs,j<-[0..100000]] $ \(i,wi,vi,j) ->
        writeArray dp (i,j) =<< if j-vi < 0 then readArray dp (i-1,j)
        else min.(+wi).min (maxBound-wi) <$> readArray dp (i-1,j-vi) <*> readArray dp (i-1,j)
    maximum.map fst.filter ((<=w).snd) <$> mapM (liftM2 fmap (,) (readArray dp.(,) n)) [0..100000]
