설명
철수는 유명한 강연자이다. 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알고리즘으로 접근했습니다.