import Control.Applicative
import qualified Data.IntMap.Strict as Map

main = do
  [_,capa] <- map (read :: String -> Int) . words <$> getLine
  goods <- map (map (read :: String -> Int) . words) . lines <$> getContents
  let maxValue = foldl1 (+) $ map head goods
  let ans = resolve capa maxValue (Map.fromList (zip [0..maxValue] [0,0..])) goods
  print $ if Ma.null ans then 0 else fst $ Map.findMax ans

resolve capa maxValue valueMap ([v,w]:xs)
  | xs == []  = Map.filter (>0) koushin'
  | otherwise = resolve capa maxValue koushin' xs
  where
    koushin'
      | capa < w  = valueMap
      | otherwise = koushin valueMap [v,w] (maxValue-v)
    koushin valueMap [v,w] n
      | n == 0 && valueMap Map.! v > w        = Map.insert v w valueMap
      | n == 0 && oldWight == 0              = Map.insert v w valueMap
      | n == 0                                = valueMap
      | oldWight == 0                         = next
      | w + oldWight > capa                  = next
      | (w + oldWight >= newWight) && newWight /= 0 = next
      | otherwise = koushin (Map.insert (n+v) (w + oldWight) valueMap) [v,w] (n-1)
      where
        oldWight = valueMap Map.! n
        newWight =valueMap Map.! (n+v)
        next     = koushin valueMap [v,w] (n-1)