题目描述

五一来临，某地下超市为了便于疏通和指挥密集的人员和车辆，以免造成超市内的混乱和拥挤，准备临时从外单位调用部分保安来维持交通秩序。 已知整个地下超市的所有通道呈一棵树的形状；某些通道之间可以互相望见。总经理要求所有通道的每个端点（树的顶点）都要有人全天候看守，在不同的通道端点安排保安所需的费用不同。 一个保安一旦站在某个通道的其中一个端点，那么他除了能看守住他所站的那个端点，也能看到这个通道的另一个端点，所以一个保安可能同时能看守住多个端点（树的结点），因此没有必要在每个通道的端点都安排保安。 编程任务： 请你帮助超市经理策划安排，在能看守全部通道端点的前提下，使得花费的经费最少。

输入格式

第 1 行 n，表示树中结点的数目。 第 2 行至第 n+1 行，每行描述每个通道端点的信息，依次为：该结点标号 i（0<i≤n），在该结点安置保安所需的经费 k（1≤k≤10000），该点的儿子数 m，接下来 m 个数，分别是这个节点的 m 个儿子的标号 r1,r2,...,rm。 对于一个 n（0<n≤1500）个结点的树，结点标号在 1 到 n 之间，且标号不重复。

输出格式

输出一行一个整数，表示最少的经费。

样例

输入样例 1

6
1 30 3 2 3 4
2 16 2 5 6
3 5 0
4 4 0
5 11 0
6 5 0

输出样例 1

25

输入样例 2

1
1 5 0

输出样例 2

5

输入样例 3

3
1 10 1 2
2 5 1 3
3 3 0

输出样例 3

5

提示

样例分析：在结点 2,3,4 安置 3 个保安能看守所有的 6 个结点，需要的经费最小：25。