import Data.Array((!),array)

calc numberOfItems goods = knapsackArray ! numberOfItems
  where
    knapsackArray = array (0, numberOfItems) [(weightSum, maximum $ map (test weightSum knapsackArray) goods)
                                             | weightSum <- [0..numberOfItems]]
      where
        test weightSum arr [itemValue,itemWeight]
          | weightSum < itemWeight = 0
          | otherwise  = arr ! (weightSum - itemWeight) + itemValue

main = do
  n' <- getLine

-- numberOfItems
  let numberOfItems = read  $ last $ words n'

  g' <- getContents

-- goods
  let goods = map (map (read :: String -> Int)) $ map words $ lines g'

  print $ calc numberOfItems goods