import Control.Applicative
import qualified Data.Vector.Unboxed as V

main = do
  [_,capa] <- map (read :: String -> Int) . words <$> getLine
  goods <- map (map (read :: String -> Int) . words) . lines <$> getContents
  print $ V.maximum (resolve capa (V.enumFromStepN 0 0 (capa+1)) goods)

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