27107번 - Garage Sailing 다국어채점 준비 중

문제

The cows have boarded their station wagon to head to town for their annual shopping trip at garage sales. They have peculiar tastes and shop only for artistic objects that are pretty much the same size.

While peculiar, their tastes are impeccable and they have the uncanny ability to know exactly how much a given object will fetch on the open market. Sometimes, they can sell the objects for a profit.

Given the labeled price and the actual value for a set of objects, calculate the greatest possible profit the cows can make, given that only K of the objects will fit in the station wagon. Of course, the cows can buy only one of each type of object.

입력

• Line 1: two integers:
  • K, 1 ≤ K ≤ 100, the number of objects that will fit in the station wagon
  • N, 1 ≤ N ≤ 100, the number of objects at the sale
• Lines 2..N+1: two space-separated integers denoting respectively the price of the object at the garage sale and the price of the object on the open market

출력

A single line containing one integer, the largest possible profit given the constraints.

제한

힌트