题目描述

$S$ 国正在进行核武器试验，数以亿计的科学家们前来观测。

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

输入格式

第一行输入一个正整数 $n$，表示点的数量，接下来 $n$ 行，每行一个描述：

第 $i+1$ 行第一个数字 $a_{i}$，表示 $i$ 号节点的儿子数；

接下来 $2a_{i}$ 个数，第 $2j-1$ 个数 $b_{i,j}$ 表示 $i$ 号节点的孩子；

第 $2j$ 个数 $c_{i,j}$ 表示其与 $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\leq n\leq 10000，0\leq c_{i,j}，t_i\leq 100000$，本题均为随机数据（树深度较小）。