UVA1222 Bribing FIPA

在 FIPA 即将有一场投票来决定下一届 IPWC 的举办地，而某个国家的代表想通过赠送钻石争取其他国家的投票。他已经知道了争取到每一个国家的选票各需要的钻石的数量，但是因为有一些贫弱的国家会与其直接或间接附属于的大国投相同国家的票，所以他不需要给每一个国家钻石以争取选票。 比如，C 国家附属于 B 国家，而 B 国家附属于 A 国家，则在向 A 国家赠送礼物后，可以获得 A、B、C 三国的选票。已知不存在一个国家附属于多个国家，且附属关系之间不存在环，试求在 $N$ 个国家中获得至少 $M$ 个国家的选票最少需要花费的钻石数量。

**本题有不定组数的多组数据。** 每组数据第一行两个整数 $N,M$，含义见题目描述。 接下来 $N$ 行，每行描述一个国家，依次为：一个字符串 $s_i$，表示国家的名称；一个数字 $a_i$，表示需要的钻石数量；若干个字符串 $t_{i,1},t_{i,2},t_{i,3},\dots,t_{i,k_i}$ 表示该国家的直接附属国（注意直接附属国的数量 $k_i$ **不会**在输入中直接给出）。 总输入以一行一个 `#` 号结束。

对于每组输入数据，输出一行表示答案。

对于 $100\%$ 的数据，$1 \leq N \leq 200$，$0 \leq M \leq N$，$1 \leq |s_i| \leq 100$。