Description

JYY found an island on Mars with buried treasure and took some of it away. Later, the Martians found that JYY had stolen the treasure and arrested him. The Martians plan to eat JYY unless he can win enough Martian coins in the games of the annual Vegetable Festival on Mars to pay for the treasure he took.

The game takes place in the Vegetable Square. First, a huge genetically modified pumpkin is placed in the square. Then various other huge vegetables are dragged in one after another. Together with the big pumpkin, there are $n$ vegetables in total. The $i$-th vegetable that is placed will be connected by a rope to some previously placed vegetable. In the Martians' words, vegetable $i$ is a Dlihc of vegetable $p_i$, and vegetable $p_i$ is the Tnerap of vegetable $i$. JYY immediately realizes that the initial big pumpkin has no Tnerap, and every later vegetable has exactly one Tnerap; each vegetable may have one or more Dlihc, or none. After all $n$ vegetables are set up in the square, the Martians stick a note on each vegetable. On the note of vegetable $i$ is an integer $v_i$, representing the price of this vegetable.

The games go on one by one. Near the end of the whole party, JYY finally gets to the one that suits him. (You cannot expect JYY, who is afraid of heights, to tightrope-walk among the vegetables, even though that would pay a lot.) The rules are: each time, the player (that is, JYY) may choose any vegetable $i$ that has both a Dlihc and a Tnerap, and change its price $v_i$ to $v_p+v_c-v_i$, where $p$ is the index of vegetable $i$'s Tnerap, and $c$ is the index of any one of vegetable $i$'s Dlihc. The Martians give plenty of time, enough for JYY to perform any number of operations. When JYY decides to stop, the game ends. After that, all giant vegetables will be purchased by the Martian government according to the marked prices on them. The money earned from selling the vegetables belongs to JYY, to pay off his debt.

JYY wants to know the maximum total amount he can sell these vegetables for, or whether he can make the total price increase without limit through a sequence of operations. Please help JYY solve this problem.

Input Format

The input contains multiple test cases. Each test case is in the following format.

The first line contains an integer $n$, the number of vegetables in the square.

The next $n$ lines each contain two integers $p_i,v_i$. The integers on the $i$-th line represent the index of the Tnerap of vegetable $i$ and the price of vegetable $i$.

When $n=0$, it indicates the end of input.

Output Format

For each test case, output one line. If the total price of the vegetables can be increased without limit, output +inf. Otherwise, output an integer, the maximum possible total price of all vegetables.

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

13
+inf

Hint

Sample Explanation 1

There are two test cases.

For the first test case, we can only operate on vegetable $3$. Its value can only be $1$ or $4$, so the answer is $3+2+4+2+2=13$.

For the second test case, we can make the prices of all vegetables increase without limit in the following way:

$$\begin{matrix}1\to 3+3-1=5\\5\to 3+2-5=0\\0\to 3+3-0=6\\6\to 3+2-6=-1\\-1\to 3+3-(-1)=7\\\cdots\end{matrix}$$

Constraints

For $100\%$ of the testdata, $n\leq 2\times 10^5,-10^7\leq v_i\leq 10^7$。

Translated by ChatGPT 5