#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
const int MAX = 422;
const int INF = 1e8;
struct edge{
	int v,next;
}Edge[MAX*2];
int head[MAX];
int ecnt = 1;
int dp[MAX][MAX];//dp[u][i]表示在u点，收买i个国家所花费的最小值 
int d[MAX];
int N,M;
char str[2222];
char name[111];
void add_edge(int u,int v)
{
	Edge[ecnt].v = v;
	Edge[ecnt].next = head[u];
	head[u] = ecnt++;
}
int vv[MAX];
int cnt = 0;//顶点数
int ans = 0;
int ischild[MAX];//是否有父亲 
void dfs(int u)
{
	fill(dp[u],dp[u]+MAX,d[u]);
	dp[u][0] = 0;
	for(int i = head[u];i;i = Edge[i].next)
	{
		int v = Edge[i].v;
		dfs(v);
		vv[u] += vv[v];
		for(int S = vv[u];S >= 1;S--)
		{
			for(int j = 0;j <= S && j <= vv[v];j++)
			{
				dp[u][S] = min(dp[u][S],dp[u][S-j] + dp[v][j]);
			}
		}
	}
	vv[u] ++;
	dp[u][vv[u]] = d[u];
} 
main()
{
	while(1)
	{
		gets(str);
		if(str[0] == '#')
		{
			break;
		}
		sscanf(str," %d%d",&N,&M);
		ecnt = 1;
		memset(head,0,sizeof(head));
		memset(ischild,0,sizeof(ischild));
		memset(vv,0,sizeof(vv));
		ans = INF;
		cnt = 0;
		map<string,int> mp;
		mp.clear();
		for(int i = 0;i < N;i++)
		{
			gets(str);
			int t = 0;
			int step = 0;
			int host = 0;
			while(~sscanf(str+t," %s",name))	
			{
				if(step == 0)
				{
					if(mp[name] == 0)
					{
						mp[name] = ++cnt;
						host = cnt;
					}
					else
					{
						host = mp[name];
					}
					step = 1;
				}
				else if(step == 1)
				{
					d[host] = atoi(name);
					step = 2;
				}
				else
				{
					if(mp[name] == 0)
					{
						mp[name] = ++cnt;
					}
					add_edge(host,mp[name]);
					ischild[mp[name]] = 1 ;
				}
				t += strlen(name);
				while(str[t]==' ')	++t;
			}
		}
		for(int i = 1;i <= cnt;i++)
		{
			//cout<<ischild[i]<<endl;
			if(!ischild[i]) add_edge(cnt+1,i);
		}
		cnt++;
		d[cnt] = INF;
		
		//cout<<cnt<<endl;
		//cout<<Edge[1].next<<endl;
		dfs(cnt);
		int res = INF;
		for(int i = M;i <= vv[cnt];i++)
		{
			res = min(res,dp[cnt][i]);
		}
		cout<<res<<endl;
	}
	return 0;
 }