题目描述

国际编程协会(FIPA)即将举行投票，决定下一届国际编程世界杯(IPWC)的主办国。钻石之地的代表团成员本杰明·贝内特正试图争取其他代表团的支持，以获得在钻石之地举办IWPC的选票。本计划通过赠送钻石来收买选票。他已经掌握了每个国家的"投票价格"。然而，他知道没有必要收买每一个国家，因为一些贫穷的小国会听从其宗主国的投票指令。因此，如果你收买了一个国家，你将同时获得其统治下所有国家（包括直接统治和间接统治）的选票。例如，如果C国受B国统治，而B国又受A国统治，那么只需收买A国就能获得这三个国家的选票。注意，任何国家最多只受一个国家的统治，且统治关系不会形成循环。你需要帮助本杰明（作为回报将获得一颗大钻石），编写一个程序计算出至少获得$m$张选票所需的最小钻石数量。由于钻石之地是候选国，因此不参与投票过程。

输入

输入包含多个测试用例。每个测试用例以一行两个整数$n$（$1 \leq n \leq 200$）和$m$（$0 \leq m \leq n$）开始，分别表示参与投票的国家数量和钻石之地需要获得的票数。接下来的$n$行，每行描述一个国家，格式如下：

国家名称 钻石数量 宗主国1 宗主国1 ...

国家名称(CountryName)是一个长度在1到100个字母之间的字符串，钻石数量(DiamondCount)是一个正整数，表示收买该国家及其所有属国（即列表中列出的宗主国1、宗主国1...）所需的钻石数量。注意，有些国家可能没有任何属国。输入结束以一个单独的#字符标记。

输出

对于每个测试用例，输出一行数字，表示获得至少$m$张选票所需的最小钻石数量。

输入样例1

3 2
Aland 10
Boland 20 Aland
Coland 15
#

输出样例1

20

来源

2006年德黑兰区域赛