import Control.Monad
import Control.Monad.State
import Control.Applicative
import qualified Data.Map as M

type Value = Int
type Weight = Int
type Item = (Weight, Value)
type Knapsack = [Item]
type Capacity = Int
type Table a b = M.Map a b
type Memo a b = State (Table a b) b

main :: IO ()
main = do
  input <- getContents
  let nums = map ((\x -> (last x, head x)) . map (read :: String -> Int) . words) . lines $ input
      capacity = fst . head $ nums
      items = tail nums
  print $ runDP (capacity, items)

memoise :: Ord a => (a -> Memo a b) -> a -> Memo a b
memoise f x = do
  table <- get
  case (M.lookup x table) of
    Just y -> return y
    Nothing -> do
      fx <- f x
      table' <- get
      put (M.insert x fx table')
      return fx

runM :: (a -> Memo a b) -> a -> b
runM m v = evalState (m v) M.empty

dp :: (Capacity, Knapsack) -> Memo (Capacity, Knapsack) Int
dp (_, []) = return $ 0
dp (b, i:is)
  | b < fst i = memoise dp (b, is)
  | otherwise = memoise dp' (b, i:is)

dp' :: (Capacity, Knapsack) -> Memo (Capacity, Knapsack) Int
dp' (b, i:is) = do
  x <- dp (b, is)
  y <- dp (b - fst i, is)
  return $ max x $ y + snd i

runDP = runM dp