Straps

Interview

Time limit1sMemory limit512 MB

Summary

Choose a set of straps forming a rooted tree: each strap occupies one port of its parent, one strap hangs from the phone, and total happiness is maximized.

Level: Medium6 of 10
Topics: Dynamic programming, Tree, DFS, Sorting
Solved: No attempts yet

Problem

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

His straps are a little unusual: some straps have several ports for attaching other straps. Each strap can be attached directly to the mobile phone, or to a port of another strap. At most one strap can be attached directly to the mobile phone.

Also, each strap has a fixed happiness value obtained when it is attached. This happiness is given as a single integer. JOI dislikes some straps, and for those the happiness is negative.

JOI wants to maximize the sum of the happiness values of the straps connected to the mobile phone. Not every port needs to have a strap attached, and attaching no straps at all is allowed.

You are given information about the N straps JOI has. Write a program that finds the maximum possible sum of the happiness values of the straps connected to the mobile phone when the straps are attached appropriately.

Input

Read the following data from standard input.

The first line contains the integer N. N is the number of straps.
In the following N lines, the i-th line (1 ≤ i ≤ N) contains the integers Ai and Bi separated by a space. This means that strap i has Ai ports, and the happiness obtained when strap i is attached is Bi.

Output

Print to standard output, on one line, the integer representing the maximum sum of the happiness values of the straps connected to the mobile phone.

Constraints

1 ≤ N ≤ 2 000.
0 ≤ Ai ≤ N (1 ≤ i ≤ N).
−1 000 000 ≤ Bi ≤ 1 000 000 (1 ≤ i ≤ N).

Examples3

Example 1
Input
```
5
0 4
2 -2
1 -1
0 1
0 3
```
Expected output
```
5
```
Example 2
Input
```
6
2 -3
3 -1
0 -4
0 -2
1 -3
4 -1
```
Expected output
```
0
```

Example 3

Input

Expected output