2609. [河南省队2016]有趣的游戏

【题目描述】

阿法汪和贝塔喵是两个绝顶聪明的AI，如今他们在玩一个很有趣的游戏。

游戏规则是这样的：有一棵有根树，这颗树的每个叶子上都有一个金币，每个金币都有各自的价值Wi。最开始，有一枚棋子在根节点，阿法汪和贝塔喵轮流走棋，每次可以将棋子从当前节点移动到它的某个儿子节点上，直到到达某个叶子，阿法汪就能获得叶子上的金币。

阿法汪希望自己获得的金币价值尽量大，而贝塔喵希望阿法汪获得的金币价值尽量小。由于两个AI都是非常聪明的，所以它们总会采用最优秀的策略。现在我们希望知道，阿法汪最终能获得价值为多少金币。

【输入格式】

第一行包含一个整数n，表示这颗树的节点数。

接下来n行中，第i行第一个整数Vi表示第i个节点有Vi个儿子。

如果Vi > 0 则接下来有Vi个整数，表示第i个节点的Vi个儿子

如果Vi = 0则接下来还有一个整数，表示第i个节点上的金币的价值W

我们规定1号节点是这颗树的根节点

【输出格式】

输出一个整数，表示阿法汪最终能获得的金币的价值

【样例输入】

10

2 2 4

2 3 5

0 -100

3 6 7 9

0 -200

0 100

2 8 10

0 -50

0 200

0 50

【样例输出】

50

【样例说明】

树的形态是这样的，最终棋子会走到10号节点

【提示】

以上是原题数据范围，鉴于该题当场AC人数过半（实际上是Mike太懒），本题数据范围的为10号描述的那样。

【来源】

2016河南省队集训，数据是Mike造的，如果数据有误请联系Mike，谁有官测直接刷掉就好。