#3447. 贿赂FIPA 暂未评定

时间限制:1000 ms 内存限制:256 MiB 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: root

题目描述

FIPA(国际国际计划协会联合会)近期将进行投票,以确定下一届IPWC(国际规划世界杯)的主办方。

钻石大陆的代表本内特希望通过以赠送钻石买通国家的方式,获得更多的投票。

当然,他并不需要买通所有的国家,因为小国家会跟随着他们附庸的大国进行投票。

换句话说,只要买通了一个大国,就等于获得了它和它统治下所有小国的投票。

例如,C在B的统治下,B在A的统治下,那么买通A就等于获得了三国的投票。

请注意,一个国家最多附庸于一个国家的统治下,附庸关系也不会构成环。

请你编写一个程序,帮助本内特求出在至少获得m个国家支持的情况下的最少花费是多少。

输入格式

输入包含多组测试数据。

第一行包含两个整数n和m,其中n表示参与投票的国家的总数,m表示获得的票数。

接下来n行,每行包含一个国家的信息,形式如下:

CountryName DiamondCount DCName DCName …

其中CountryName是一个长度不超过100的字符串,表示这个国家的名字,DiamondCount是一个整数,表示买通该国家需要的钻石数,DCName是一个字符串,表示直接附庸于该国家的一个国家的名字。

一个国家可能没有任何附庸国家。

当读入一行为#时,表示输入终止。

输出格式

每组数据输出一个结果,每个结果占一行。

样例

样例输入

3 2
Aland 10
Boland 20 Aland
Coland 15
#

样例输出

20

数据范围与提示

,

POJ 3345