JOI has $N$ straps for a mobile phone. The straps are numbered from $1$ to $N$. JOI is planning to attach some of these straps to his mobile phone.

The straps JOI has are a bit unusual; some straps have several terminals for attaching other straps. Each strap can either be attached directly to the mobile phone or to a terminal of another strap. At most one strap can be attached directly to the mobile phone.

Additionally, each strap has a fixed "happiness" value associated with it when attached. This happiness is represented by an integer. Some straps are disliked by JOI, in which case the happiness value is negative.

JOI wants to maximize the total sum of happiness of the straps connected to the mobile phone. Note that it is not necessary to attach a strap to every terminal, and it is also acceptable to attach no straps at all.

Task

Given the information about the $N$ straps JOI has, write a program to calculate the maximum total sum of happiness 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 an integer $N$, representing the number of straps.
• The $i$-th line of the following $N$ lines ($1 \le i \le N$) contains two space-separated integers $A_i$ and $B_i$. This means that strap $i$ has $A_i$ terminals, and the happiness gained when attaching this strap is $B_i$.

Output

Output the maximum total sum of happiness of the straps connected to the mobile phone as an integer on a single line.

Constraints

All input data satisfies the following conditions:

• $1 \le N \le 2\,000$
• $0 \le A_i \le N$ ($1 \le i \le N$)
• $-1\,000\,000 \le B_i \le 1\,000\,000$ ($1 \le i \le N$)

Subtasks

1. (5 points) $N \le 15$ is satisfied.
2. (5 points) $B_i \ge 0$ ($1 \le i \le N$) is satisfied.
3. (45 points) $A_i \le 15$ ($1 \le i \le N$) is satisfied.
4. (45 points) No additional constraints.

Examples

Input 1

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

Output 1

5

Note In this case, the total happiness is maximized to $5$ by attaching the straps as follows: Attach strap $2$ directly to the mobile phone. Attach strap $1$ to a terminal of strap $2$. * Attach strap $5$ to a terminal of strap $2$.

Input 2

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

Output 2

0

Note In this case, the happiness of every strap is less than $0$. Therefore, the total happiness is maximized when no straps are attached.

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

Output 3

43417