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)
inf=maxBound`div`2
main=do
    [n,w]<-map read.words<$>getLine
    wvs<-UV.replicateM n $ r2.unfoldr(B.readInt.B.dropWhile(<'!'))<$>B.getLine
    print $ f w wvs
f::Int->UV.Vector (Int,Int)->Int
f w wvs = UV.length $ UV.takeWhile(<=w) $ UV.foldl' p (UV.replicate 100000 inf) wvs where
    p v0 (wi,vi) = UV.zipWith min v0 (UV.replicate vi wi UV.++ UV.map (+wi) v0)
