과제

면접 대비

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

요약

마감일과 점수가 주어진 N개의 과제 중 마감일 안에 끝낼 수 있는 부분집합을 골라 총점을 최대로 만든다.

난이도: 보통10점 중 5점
유형: 그리디, 정렬, 힙, 구간
정답자: 아직 제출이 없습니다

문제

웅찬이는 끝내야 할 과제가 많다. 하루에 과제를 하나씩 끝낼 수 있고, 과제마다 마감일이 정해져 있어서 모든 과제를 끝내지 못할 수도 있다. 과제를 끝내면 그 과제에 걸린 점수를 얻지만, 마감일이 지난 과제는 점수를 받을 수 없다.

웅찬이가 얻을 수 있는 점수의 최댓값을 구하시오.

입력

첫째 줄에 과제의 개수 $N$ ( $1 \le N \le 1000$ )이 주어진다.

둘째 줄부터 $N$ 개의 줄에 과제 하나의 정보가 두 정수 $d$ ( $1 \le d \le 1000$ )와 $w$ ( $1 \le w \le 100$ )로 주어진다. $d$ 는 마감일까지 남은 일수로, 이 과제는 첫째 날부터 $d$ 째 날 사이에만 끝낼 수 있다. $w$ 는 그 과제를 끝냈을 때 얻는 점수다.

출력

얻을 수 있는 점수의 최댓값을 첫째 줄에 출력한다.

힌트

첫 번째 예제에서는 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제를 이 순서로 끝내고 세 번째와 여섯 번째 과제를 포기하면 185점을 얻는다.

예제6

예제 1

입력

예상 출력

예제 2
입력
```
1
1 1
```
예상 출력
```
1
```
예제 3
입력
```
1
1000 100
```
예상 출력
```
100
```
예제 4
입력
```
4
1 10
1 20
1 5
1 30
```
예상 출력
```
30
```
예제 5
입력
```
5
5 1
5 2
5 3
5 4
5 5
```
예상 출력
```
15
```
예제 6
입력
```
3
1 5
2 5
3 5
```
예상 출력
```
15
```