7459: BZOJ3459：Bomb

S国正在进行核武器试验，数以亿计的科学家们前来观测。试验区位于S国某城市，此城市有n个区域，共有n-1条道路连接它们，任意两片区域可相互到达。其中核弹将于某个区域引爆，科学家们将去往一些度数为1的非引爆点区域，即观测点观察。抽象的说，若将此引爆区域设为有根树的根，科学家们将去往非根叶子节点。所有科学家可以同时行动，每条道路双向通行，且均给出一个所需通过的时间，然而每个观测点容纳人数有限，但是保证观测点容量大于等于科学家数。求科学家们最少所需移动时间，以使试验尽早开始。

输入格式

　　第一行输入一个正整数n，表示点的数量，接下来n行，每行一条描述。
　　第i+1行第一个数字a_i，表示i号节点的儿子数。接下来2a_i个数，第2j-1个数b_ij表示i号节点的孩子，第2j个数c_ij表示其与i之间边权。接下来一个数t_i，若a_i等于0，表示此点最多可容纳人数，若a_i不等于0，则表示此点现有人数。

输出格式

　　一个数，表示最少所需时间。

样例输入

4
2 2 5 3 3 2
1 4 2 3
0 2
0 3

样例输出

3

提示

　　100%的数据1<=n<=10000，0<=cij，ti<=100000，本题均为随机数据（树深度较小）。

题目来源

没有写明来源