문제

설명

철수는 유명한 강연자이다. N개이 기업에서 강연 요청을 해왔다. 각 기업은 D일 안에 와서 강연을 해 주면 M만큼의 강연료를 주기로 했다.

각 기업이 요청한 D와 M를 바탕으로 가장 많을 돈을 벌 수 있도록 강연 스케쥴을 짜야 한다.

단 강연의 특성상 철수는 하루에 하나의 기업에서만 강연을 할 수 있다.

입력

첫 번째 줄에 자연수 N(1<=N<=10,000)이 주어지고, 다음 N개의 줄에 M(1<=M<=10,000)과 D(1<=D<=10,000)가 차례로 주어진다.

출력

첫 번째 줄에 최대로 벌 수 있는 수입을 출력한다.

예시 입력 1

6
50 2
20 1
40 2
60 3
30 3
30 1

예시 출력 1

150

예시입력 2

5
3 2
65 1
61 3
60 2
86 1

예시출력 2

207

문제 접근

기간을 내림차순으로 정렬한 후, N일차에 선택할 수 있는 가장 큰 수입의 강의, N-1일차에 선택할수 있는 가장큰 수입의 강의 ... 1일차에 선택할 수 있는 가장 큰 수입의 강의를 구하는 Greedy알고리즘으로 접근했습니다.