Задача D. Выбор вершин взвешенного дерева ≡

Условие

Дан граф, являющийся деревом. В вершинах графа написаны целые числа. Множество вершин графа называется допустимым, если никакие две вершины этого множества не соединены ребром.

Рассмотрим все допустимые множества вершин графа. Для каждого такого множества вычислим сумму чисел, написанных в его вершинах. Какова максимальная из этих сумм?

Формат входного файла

Граф в этой задаче задан в виде корневого дерева. В графе выделена вершина — корень дерева. Для каждой вершины i, не являющейся корнем, задан номер вершины-предка p_i в корневом дереве. Дерево, заданное таким образом, состоит из рёбер i — p_i для всех вершин i, кроме корня.

В первой строке входного файла записано целое число n  — количество вершин в графе . В следующих n строках задан граф. В i-й из этих строк записаны через пробел два целых числа p_i и q_i; здесь p_i  — номер вершины-предка i-ой вершины, а q_i  — число, записанное в этой вершине. Для корня дерева p_i = 0; для всех остальных вершин 1 ≤ p_i ≤ n.

Гарантируется, что заданный во входном файле граф является деревом.

Формат выходного файла

В первой строке выходного файла выведите одно число — максимальную сумму чисел в допустимом множестве.

Ограничения

1 ≤ n ≤ 100

1 ≤ p_i ≤ n

|q_i| ≤ 10⁴

Примеры тестов

5
0 1
1 2
1 3
2 4
3 5

10

6
5 8
6 0
5 -1
1 1
0 3
1 2

8