CF533B.Work Group

One Big Software Company has n employees numbered from 1 to n. The director is assigned number 1. Every employee of the company except the director has exactly one immediate superior. The director, of course, doesn't have a superior.

We will call person a a subordinates of another person b, if either b is an immediate supervisor of a, or the immediate supervisor of a is a subordinate to person b. In particular, subordinates of the head are all other employees of the company.

To solve achieve an Important Goal we need to form a workgroup. Every person has some efficiency, expressed by a positive integer a__i, where i is the person's number. The efficiency of the workgroup is defined as the total efficiency of all the people included in it.

The employees of the big software company are obsessed with modern ways of work process organization. Today pair programming is at the peak of popularity, so the workgroup should be formed with the following condition. Each person entering the workgroup should be able to sort all of his subordinates who are also in the workgroup into pairs. In other words, for each of the members of the workgroup the number of his subordinates within the workgroup should be even.

Your task is to determine the maximum possible efficiency of the workgroup formed at observing the given condition. Any person including the director of company can enter the workgroup.

一家大型软件公司有 $n$ 名员工，编号从 $1$ 到 $n$。总监编号为 $1$。除总监外，公司每名员工恰好有一名直属上级；总监当然没有上级。

我们称员工 $a$ 是员工 $b$ 的下属，当且仅当：$b$ 是 $a$ 的直属上级，或 $a$ 的直属上级是 $b$ 的下属。特别地，总监的下属即为公司所有其他员工。

为实现一项重要目标，我们需要组建一个工作组。每名员工具有某个效率值（用正整数 $a_i$ 表示，其中 $i$ 为其编号）。工作组的效率定义为其中所有成员效率值之和。

这家大型软件公司的员工痴迷于现代工作流程组织方式。目前，结对编程（pair programming）正风靡一时，因此工作组必须满足如下条件：每位进入工作组的员工，都应能将其在工作组内的所有下属两两配对。换言之，对工作组中的每一位成员，其在工作组内的下属人数必须为偶数。

你的任务是：在满足上述条件的前提下，求出工作组可能达到的最大效率值。任何员工（包括公司总监）均可加入工作组。

The first line contains integer n (1 ≤ n ≤ 2·105) — the number of workers of the Big Software Company.

Then n lines follow, describing the company employees. The i-th line contains two integers p__i, a__i (1 ≤ a__i ≤ 105) — the number of the person who is the i-th employee's immediate superior and i-th employee's efficiency. For the director _p_1 =  - 1, for all other people the condition 1 ≤ p__i < i is fulfilled.

第一行包含一个整数 $n$（$1 \leq n \leq 2 \cdot 10^5$）—— 大软件公司员工的数量。

接下来有 $n$ 行，描述公司员工的信息。第 $i$ 行包含两个整数 $p_i$、$a_i$（$1 \leq a_i \leq 10^5$）—— 分别表示第 $i$ 号员工的直属上级编号以及第 $i$ 号员工的工作效率。对于公司总监（即第 $1$ 号员工），有 $p_1 = -1$；对于其余所有员工，均满足 $1 \leq p_i < i$。

Print a single integer — the maximum possible efficiency of the workgroup.

输出一个整数——工作组可能达到的最大效率。

In the sample test the most effective way is to make a workgroup from employees number 1, 2, 4, 5, 6.

在样例测试中，最有效的方法是选择编号为 1、2、4、5、6 的员工组成一个工作组。