{-# OPTIONS_GHC -O2 -fexpose-all-unfoldings #-}
import Control.Applicative
import qualified Data.HashMap.Strict as Map

main = do
    [_,capa] <- map (read :: String -> Int) . words <$> getLine
    goods <- map (map (read :: String -> Int) . words) . lines <$> getContents
    print $ maximum $ map snd $ Map.toList (resolve capa (Map.fromList (zip [0..capa] [0,0..])) goods)

resolve capa capaMap ([v,w]:xs)
  | xs == []  = koushin'
  | otherwise = resolve capa koushin' xs
  where
    koushin' =  koushin capaMap [v,w] 0
    koushin capaMap [v,w] n
      | n == 0 && capaMap Map.! w <= v      = next'
      | n > (capa - w)                      = capaMap
      | capaMap Map.! (n+w) >= v + oldValue = next
      | otherwise                           = next'
      where
        oldValue = capaMap Map.! n
        next     = koushin capaMap [v,w] (n+1)
        next'    = koushin (Map.insert (n+w) (v + oldValue) capaMap) [v,w] (n+1)