import Control.Monad
import Control.Applicative
import Data.List
import Data.Array.IO

type Value = Int
type Weight = Int
type Item = (Weight, Value)
type ItemList = [Item]
type Capacity = Int

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
  memo <- newArray ((0, 0), (capacity, length items)) (0 - 1) :: IO (IOUArray (Int, Int) Int)
  dp (capacity, items) memo
  putStrLn . show . last =<< getElems memo

memoize :: ((Capacity, ItemList) -> IOUArray (Int, Int) Int -> IO (IOUArray (Int, Int) Int)) -> (Capacity, ItemList) -> IOUArray (Int, Int) Int -> IO (IOUArray (Int, Int) Int)
memoize f (c, i) t = do
  v <- readArray t (c, length i)
  if v < 0
    then do
      return =<< f (c, i) t
    else return t

dp :: (Capacity, ItemList) -> IOUArray (Int, Int) Int -> IO (IOUArray (Int, Int) Int)
dp (c, []) t = do
  writeArray t (c, 0) 0
  return t
dp (c, i:is) t
  | c < fst i = memoize dp (c, is) t
  | otherwise = memoize dp' (c, i:is) t

dp' (c, as@(i:is)) t
  | c < fst i = dp (c, is) t
  | otherwise = do
    x <- dp (c, is) t
    y <- dp (c - fst i, is) t
    xv <- readArray t (c, length is)
    yv <- readArray t (c - fst i, length is)
    writeArray t (c, length as) (max xv $ yv + snd i)
    return t