题目描述

热带岛屿 Lagrishan 的首领现在面临一个问题：几年前，一批外援资金被用于维护村落之间的道路，但日益繁茂的丛林无情的侵蚀着村民的道路，导致道路维修开销巨大，长老会不得不放弃部分道路的维护。已经知道了每条路每个月的维修费用（单位为\(aacms\)）。现在长老会需要提出一种方案，即需要保证村落之间都可以互相到达，又要将每个月的道路维修费用控制在最小。村子编号为从 \(A\) 到 \(I\)。上图右侧显示的方案最小维修开销为 \(216\) \(aacms\) 每月。

格式

输入格式

输入包含 \(1\) ~ \(50\) 个数据集，最后一行为 \(0\).每个数据集第一行为村落数目\(n,1 < n < 27\),依次用字母表的前 \(n\) 个字母标记。接下来有 \(n-1\) 行，每行的第一个数据便是按字母顺序排列的村子编号（不包括最后一个村庄）。每个村庄后面的数据 \(k\) 代表该村庄通往编号在其之后的村庄的道路数目，如 A 2 B 12 I 25，代表 \(A\) 村庄有 \(2\) 个编号在 \(A\) 之后的村庄和其相连。若 \(k\) 大于 \(0\)，\(k\) 后面会依次给出这 \(k\) 个村庄的编号以及各自到起始村庄的道路维修费用，如A 2 B 12 I 25，代表 \(A\) 和 \(B\) 之间道路维修费用为 \(12\)， \(A\) 和 \(I\) 之间道路维修费用为 \(25\)（维修费用为不超过 \(100\) 的正整数）.路的总数目不超过 \(75\) 条，每个村庄到其他村庄不会有超过 \(15\) 条路（包括编号在其之前和之后的）。

输出格式

每个数据集有一个输出：针对解决方案每个月维修道路的小费用。

提示：蛮力算法虽能找出解决方案，但将会超出时间限制。

样例1

样例输入1

9
A 2 B 12 I 25
B 3 C 10 H 40 I 8
C 2 D 18 G 55
D 1 E 44
E 2 F 60 G 38
F 0
G 1 H 35
H 1 I 35
3
A 2 B 10 C 40
B 1 C 20
0

样例输出1

216
30

限制

时间：\(1s\) 空间：\(64M\)

来源

地址：\(zloj,J2020\)域
作者：\(jialiang2509\)
模拟赛\(T2\)