Define a particular type of arrays as perfect if:

• Consisting of -1 and 1;
• The sum of any of its prefix is not less than 0;
• The sum of the entire array is 0.

For example, the following arrays are perfect:

• 1 1 1 -1 -1 -1
• 1 -1 1 1 -1 -1

While the followings are not:

• -1 1
• 1 -1 -1 1

The NP-value of a perfect array is the maximum prefix sum occurred in the array. For example, the NP-values of the two perfect arrays above are 3 and 2 respectively.

Given a tree with either -1 or 1 assigned on each node, please figure out a simple path, that the array concatenated by values on the path is perfect along with the maximum NP-value.

Input

The input consists of multiple test cases.

Each test case begins with an integer $n$ ($1 \leq n \leq 10^6$), the number of nodes in the tree.

Then $n$ lines follow. The $i$-th line of the following $n$ lines consists of $f_i$ ($0 \leq f_i \leq n$) and $v_i$ ($v_i \in \{-1, 1\}$), which respectively denotes the parent node and the assigned value of the $i$-th node. Nodes are labeled from $1$ to $n$, and $f_i$ = 0 indicates that node $i$ is a root.

The sum of $n$ in all test cases does not exceed $5 \times 10^6$.

Output

For each test case, output the maximum NP-value found on the tree. Output 0 if such path doesn't exist.

Example

Input

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

Output

2