Cherry
A determined mouse has set its sights on eating all the cherries from a cherry tree. This tree is structured such that its branches split but never rejoin. At the end of each branch, new branches may sprout, or cherries may be found.
As the mouse travels along the branches, its energy diminishes. Specifically, for every meter the mouse crawls, it loses one unit of useful substances (US) from its body. Consuming a cherry restores one unit of US. If the mouse's US reserve drops below zero, it will not survive.
Your task is to write a program, CHERRY, that calculates the minimum initial US units the mouse needs to consume all the cherries and return safely to the ground. The mouse's US reserve must remain non-negative throughout its journey.
The journey begins and ends at the start of branch number 1, which is the trunk of the tree.
Input
The first line contains an integer N (1 ≤ N ≤ 100), representing the number of branches on the tree. The following N lines describe each branch. For the (i+1)-th line, the first number is an integer L (1 ≤ L ≤ 30000), indicating the length of the branch. The second number is K, the number of branches that extend from the end of the i-th branch. Following this are K integers, which are the indices of these branches. If K is zero, the third number specifies the number of cherries V (0 ≤ V ≤ 30000) at the end of the branch.
Output
Output a single integer: the minimum number of US units the mouse needs to start with to climb the tree, eat all the cherries, and return to the ground without its US reserve ever becoming negative.