Maximum Participation in Activity

A large enterprise group consists of N departments numbered from 1 to N. The hierarchical relationships among these departments form a tree structure: each department (except the root) has exactly one direct superior, and a superior department may have one or more direct subordinates.

This month, the group is organizing a large activity. The organizers want to maximize the number of people attending the activity. However, the arrangement must follow these rules:

1. The more people attend, the better.
2. If a department participates in the activity, then its direct subordinate departments are not allowed to participate. (However, the indirect subordinates may attend, e.g. if department 1 participates, then its direct children (departments 2 and 3) cannot participate, but the grandchildren (such as departments 4, 5, and 6) can participate.)

Each department has a certain number of people. You are given the parent-child relationships and the number of people in each department. When the top-level department is indicated with a parent value of 0 (meaning it has no superior), determine the maximum number of people that can participate in the activity by choosing a subset of departments that satisfy the above rules.

Note: The answer must be output as a single integer representing the maximum number of attendees.

Mathematical formulation:

For a department u with weight w_u (the number of people), let its children be denoted by v. Define the DP states as:

\( dp[u][1] = w_u + \sum_{v \in children(u)} dp[v][0] \)

\( dp[u][0] = \sum_{v \in children(u)} \max(dp[v][0], dp[v][1]) \)

The answer is \( \max(dp[root][0], dp[root][1]) \) summed over all root departments (in case of a forest).

inputFormat

The input starts with an integer N (1 ≤ N ≤ 10⁵), representing the number of departments. The following N lines each contain two integers. For the i-th department (1-indexed):

• The first integer is the parent id of department i. For the top-level department, the parent id will be 0.
• The second integer is the number of people in that department.

It is guaranteed that the given relationships form a tree (or forest) structure.

outputFormat

Output a single integer — the maximum number of people that can participate in the event following the given rules.

sample

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

11