Straps

JOI Spring Training Camp 2013/14
Original Statement / Submission Site

Problem Statement

JOI-kun has N straps for attaching to his mobile phone. The straps are numbered from 1 to N. He wants to attach some of these straps to his phone.

The straps are somewhat unusual. Some straps have several connectors to which other straps can be attached. Each strap can be attached either directly to the mobile phone or to a connector on another strap. At most one strap can be attached directly to the mobile phone.

Each strap has a fixed happiness value that JOI-kun gains when the strap is attached. This value is represented by an integer. JOI-kun dislikes some straps, so their happiness values may be negative.

JOI-kun wants to maximize the sum of the happiness values of all straps connected to the mobile phone. It is not necessary to attach a strap to every connector, and he may also choose not to attach any straps at all.

Task

Given information about JOI-kun's N straps, determine the maximum possible total happiness of the straps connected to the mobile phone.

Input

The input is given from standard input in the following format:

N
A1 B1
A2 B2
...
AN BN

• The first line contains an integer N, the number of straps.
• Each of the next N lines contains two integers Ai and Bi. Strap i has Ai connectors, and attaching it gives a happiness value of Bi.

Output

Print one integer: the maximum possible sum of the happiness values of all straps connected to the mobile phone.

Constraints

• 1 ≤ N ≤ 2000
• 0 ≤ Ai ≤ N
• -1000000 ≤ Bi ≤ 1000000

Subtasks

Subtask 1 [5 points]

• N ≤ 15

Subtask 2 [5 points]

• Bi = 0 for every i.

Subtask 3 [45 points]

• Ai ≤ 15 for every i.

Subtask 4 [45 points]

There are no additional constraints.

Sample Input 1

5
0 4
2 -2
1 -1
0 1
0 3

Sample Output 1

5

Explanation of Sample 1

In this case, the maximum total happiness is 5, achieved by attaching the straps as follows:

• Attach strap 2 directly to the mobile phone.
• Attach strap 1 to one connector of strap 2.
• Attach strap 5 to another connector of strap 2.

Sample Input 2

6
2 -3
3 -1
0 -4
0 -2
1 -3
4 -1

Sample Output 2

0

Explanation of Sample 2

Every strap has a negative happiness value. Therefore, the maximum total happiness is obtained by attaching no straps.

Sample Input 3

15
1 -4034
1 3406
0 6062
4 -6824
0 9798
0 4500
0 -1915
1 2137
0 9786
0 7330
0 -9365
2 2730
0 -5797
0 6129
0 8925

Sample Output 3

43417