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

import Control.Monad.Trans.State.Strict
import Data.Char (isSpace)
import Data.Maybe (fromJust)

type Parser a = StateT B.ByteString Maybe a

parseInt :: Parser Int
parseInt = StateT (B.readInt . B.dropWhile isSpace)

parseInt2 :: Parser (Int,Int)
parseInt2 = liftM2 (,) parseInt parseInt

parse :: Parser (Int, Int, [(Int,Int)])
parse = do
    n <- parseInt
    w <- parseInt
    fmap ((,,) n w) (replicateM n parseInt2)

main = do
    (n,w,wvs) <- fromJust.evalStateT parse <$> B.getContents
    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(fmap<$>(,)<*>readArray dp.(,) n)[0..100000]
