Excursion

Jimmy goes on an excursion in the country of Treenidad and Treebago. The people there are so obsessed with trees that they modeled their country after them. As a careful planner, Jimmy wants to know in advance which cities he should visit to maximize the total appeal of his excursion. The appeal of a city is an integer that may be negative. Jimmy went through a lot of trouble to get his visa, so he wants to visit at least one city. He can start the excursion from any city. When visiting the country, he must not visit the same city twice.

The first line contains an integer $1\leq n \leq 10^6$, the number of cities in Treenidad and Treebago. Then $n$ lines follow. The first of these describes the root of the tree. Each of the following lines contains two integers, $V$ and $C$, which describe the properties of a node in the tree.

• $V$ is the value at that node, with $-2^{31} \leq V < 2^{31}$.
• $C$ is the number of children of the node, with $0 \leq C < 10^6$.

After that, $C$ lines follow, each recursively defining a child tree. The height of the tree is guaranteed to be at most $990$.

Print the maximum appeal Jimmy can gather on his excursion.