{-# LANGUAGE FlexibleContexts #-}

import Control.Applicative
import Data.Array.Diff

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

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