2144: 宝典2第十一章最后一战

【题目描述】最后一战（lastwar.cpp/c/pas） tyvj 1513　

受伤的愤怒道：“你不是要做这世界之主吗？那为什么之前你不仅故意通风报信毁灭了我交给你的那些强大武装，现在还来攻击我？”

修罗王冷笑：“没错，我是不喜欢这个世界的许多规则，所以我想重新按我的规则、我的方式来改造这个世界，但这是我和这个世界的事，与你异星人无关。再说了，你觉得我修罗王，什么时候会受别人控制？”

“好吧，我承认我低估了你们人类，但你要想抓到我也是不可能的。” 天顶星人在狂笑声中消失。

此时修罗王正在一个城堡中，城堡中的路形成一棵树，每条路的结点处因地形的险要程度不同，所需要的士兵数量也不相同，只有达到需要的士兵数量，该结点才可以构成强大的火力网以对抗天顶星人，注意，若有士兵在一个结点上时，与该结点相连的所有边都可以被防守。

请你帮修罗王计算出他至少需要放置多少士兵才可以防守住所有道路。

【输入格式】

输入文件中数据表示一棵树，描述如下：

第1行 n，表示树中结点的数目。

第2行至第n+1行，每行描述每个结点信息，依次为：该结点标号i（0<i≤n），在该结点安置士兵所需的数量k，该边的儿子数m，接下来m个数，分别是这个节点的m个儿子的标号r₁，r₂，…，r_m。

对于一个n（0 < n≤ 1500）个结点的树，结点标号在1到n之间，且标号不重复。

【输出格式】

输出文件仅包含一个数，为至少需要的士兵数。

【样例输入】

6

1 30 3 2 3 4

2 16 2 5 6

3 5 0

4 4 0

5 11 0

6 5 0

【样例输出】

25