차고 세일

면접 대비

시간 제한1초메모리 제한1024 MB

요약

최대 K개의 물건을 골라 시장 가격과 세일 가격의 차이 합이 가장 크도록 하고, 그 최대 이익을 출력합니다.

문제

소들이 연례 쇼핑을 위해 스테이션 왜건을 타고 차고 세일 장터로 향한다. 소들이 사는 것은 크기가 거의 같은 예술품뿐이다.

소들은 취향이 독특하지만 안목은 뛰어나다. 어떤 물건이 공개 시장에서 얼마에 팔릴지 정확히 안다. 때로는 물건을 팔아 이익을 남길 수 있다.

차고 세일에 표시된 가격과 물건의 실제 가치가 주어졌을 때, 소들이 얻을 수 있는 최대 이익을 구하라. 스테이션 왜건에는 $K$ 개의 물건만 실을 수 있다. 같은 종류의 물건은 하나만 살 수 있다.

첫 줄에 두 정수 $K$ ( $1 \le K \le 100$ )와 $N$ ( $1 \le N \le 100$ )이 주어진다. $K$ 는 스테이션 왜건에 실을 수 있는 물건의 개수이고, $N$ 은 세일에 나온 물건의 개수이다.

이어지는 $N$ 개의 줄에는 각각 공백으로 구분된 두 정수가 주어진다. 차고 세일에서의 가격과 공개 시장에서의 가격이다.

제약 조건 아래에서 얻을 수 있는 최대 이익을 한 줄에 정수로 출력한다.