### 2017 Canadian Computing Olympiad

## Day 2, Problem 2 - Professional Network

Kevin is developing his professional network within a certain community. Unfortunately, he is not connected with anybody yet. But he has his eyes on `N` potentially valuable connections, numbered form 1 to `N`. He is determined to connect with them all.

However, few people in this community are willing to friend an outsider. Each of the `N` people Kevin wants to connect with has similar, but different criteria for determining who is an outsider and who isn't. Person `i` is willing to friend Kevin if he either has at least `A _{i}` connections within the community already, or if Kevin gives this person

`B`Internet Points.

_{i}Kevin likes his Internet Points very much, and he doesn't want to give away too many. Now it is your job to help Kevin give away the least number of Internet Points while still making connections with each of the `N` people.

### Input Format

The first line will contain the integer `N` (1 ≤ `N` ≤ 200 000). Each of the next `N` lines will contain integers `A _{i}` and

`B`(1 ≤

_{i}`i`≤

`N`; 0 ≤

`A`≤

_{i}`N`; 0 ≤

`B`≤ 10 000).

_{i}
For 2 of the 25 available marks, `B _{i}` = 1 for all

`i`.

For an additional 4 of the 25 available marks,

`N`≤ 10.

For an additional 7 of the 25 available marks,

`N`≤ 1000.

### Output Format

Output one integer on a single line, the minimum number of Internet Points Kevin has to give away.

### Sample Input 1

4 3 3 1 2 0 5 3 4

### Sample Output 1

3

### Explanation 1

Kevin can connect with person 3 immediately, and with this connection made, he can also connect with person 2. He doesn't have enough connections to connect with person 1 or person 4, so he gives 3 Internet Points to person 1 to acquire 3 total connections which enables him to connect with person 4.

### Sample Input 2

5 0 9 1 8 2 7 3 6 4 5

### Sample Output 2

0

### Explanation 2

It is possible for Kevin to connect with everyone without giving away any Internet Points.

### Sample Input 3

3 0 6 2 7 3 8

### Sample Output 3

8

### Explanation 3

Kevin should connect with person 1 immediately, then give 8 Internet Points to person 3 to connect with them, then connect with person 2.

All Submissions

Best Solutions

**Point Value:** 20 (partial)

**Time Limit:** 2.00s

**Memory Limit:** 256M

**Added:** Aug 09, 2017

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

It's quiet in here...