인맥 쌓기

면접 대비

시간 제한2초메모리 제한512 MB

요약

각 사람은 Kevin의 현재 연결 수가 A_i 이상이면 무료로, 아니면 B_i 포인트를 내면 연결된다. 모든 사람과 연결하는 최소 포인트 합을 구한다.

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

문제

케빈은 어느 커뮤니티에서 인맥을 쌓으려고 한다. 아직 아무와도 연결되어 있지 않지만, 연결할 가치가 있다고 본 사람 $N$ 명을 $1$ 번부터 $N$ 번까지 정해 두었다. 목표는 이 $N$ 명 모두와 연결되는 것이다.

이 커뮤니티에서 외부인과 친구를 맺어 주는 사람은 드물다. $N$ 명은 누구를 외부인으로 볼지 판단하는 기준이 서로 조금씩 다르다. $i$ 번 사람은 케빈이 커뮤니티 안에서 이미 $A_i$ 명 이상과 연결되어 있으면 친구가 되어 준다. 연결이 모자라더라도 케빈이 인터넷 포인트 $B_i$ 를 주면 친구가 되어 준다.

케빈은 인터넷 포인트를 아끼고 싶다. $N$ 명 모두와 연결하면서 주는 포인트의 합을 최소로 만들어라.

입력

첫째 줄에 정수 $N$ 이 주어진다 ( $1 \le N \le 200000$ ).

다음 $N$ 개 줄 중 $i$ 번째 줄에 정수 $A_i$ 와 $B_i$ 가 주어진다 ( $1 \le i \le N$ , $0 \le A_i \le N$ , $0 \le B_i \le 10000$ ).

출력

케빈이 주어야 하는 인터넷 포인트의 최솟값을 한 줄에 출력한다.

힌트

첫 번째 예제에서 케빈은 $3$ 번 사람과 바로 연결하고, 그 연결로 $2$ 번 사람과도 연결한다. $1$ 번 사람과 $4$ 번 사람은 연결이 모자라 바로 연결할 수 없으므로, $1$ 번 사람에게 포인트 $3$ 을 주어 연결을 $3$ 개로 늘린 다음 $4$ 번 사람과 연결한다.

두 번째 예제에서는 포인트를 하나도 주지 않고 모두와 연결할 수 있다.

세 번째 예제에서 케빈은 $1$ 번 사람과 먼저 연결하고, $3$ 번 사람에게 포인트 $8$ 을 주어 연결한 뒤 $2$ 번 사람과 연결한다.

예제3

예제 1
입력
```
4
3 3
1 2
0 5
3 4
```
예상 출력
```
3
```
예제 2
입력
```
5
0 9
1 8
2 7
3 6
4 5
```
예상 출력
```
0
```
예제 3
입력
```
3
0 6
2 7
3 8
```
예상 출력
```
8
```