은하 컨테이너선

화성의 한 점토 광산은 붉은 탄소-규소 점토를 캐내어 운반하기 좋은 판으로 압축한다. 모든 판의 너비와 두께는 같지만, 판마다 높이와 재질의 품질은 다를 수 있다. 품질 등급은 1000가지가 있으며, 판의 높이는 1, 2, ..., 500000mm로 생산된다. 판의 가격은 오직 재질의 품질에만 좌우되며 높이와는 무관하다. 품질 등급이 $q$인 재질로 만든 판의 가격은 $q$ 갈락타르이다.

은하 컨테이너선은 이 판들을 실어 나르는 우주선이다. 이 배의 화물칸은 바닥에 $M$개의 레일이 평행하게 설치된 넓은 홀이며, 레일 하나에는 판을 하나만 놓을 수 있다. 화물칸의 천장은 비스듬히 기울어져 있어 한쪽 끝은 높이가 $1$mm, 반대쪽 끝은 $M$mm이다. 즉 번호가 $n$인 레일 위의 천장 높이는 정확히 $n$mm이므로, 그 레일에는 높이가 $n$ 이하인 판만 놓을 수 있다.

부두에는 운반을 기다리는 판 더미가 쌓여 있다. 선장은 화물의 총 가치를 최대로 만들고 싶지만 화물칸의 크기에 제약을 받는다(판은 잘라낼 수 없다). 노련한 선원들은 언제나 선장의 뜻에 따라 화물을 최적으로 고른다. 최적의 화물에 대해 선장이 얼마를 지불해야 하는지 구하여라.

다음을 수행하는 프로그램을 작성하여라.

• 화물칸의 크기와 더미에 놓인 판들의 크기를 읽어 들인다.
• 실을 수 있는 화물의 최대 총 가치를 계산한다.
• 그 최대 가치를 출력한다.

첫째 줄에 공백으로 구분된 두 자연수 $M$과 $N$이 주어진다($1 \le M \le 500000$, $0 \le N \le 1000000$). $M$은 화물칸의 길이이자 최대 높이이며 동시에 레일의 개수이고, $N$은 더미에 놓인 판의 개수이다. 이어지는 $N$개의 줄에는 각 줄마다 판 하나의 정보가 공백으로 구분된 두 자연수 $w$와 $h$로 주어진다($1 \le w \le 1000$, $1 \le h \le 500000$). $w$는 판 재질의 품질 등급, $h$는 판의 높이(mm)이다. 더미에는 화물칸의 최대 허용 높이보다 높은 판이 섞여 있을 수도 있음에 유의하여라.

첫째 줄에 최적 화물의 가치를 나타내는 정수 하나를 출력한다.