#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
typedef long long LL;
#pragma warning(disable :4996)
typedef unsigned long long ULL;
typedef pair<int, int> PII;
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
const int maxn = 1010;
const int maxlogn = 20;
const int maxc = 1000010;
const long double eps = 1e-8;
const LL MOD = 998244353;
 
int N, M;
vector<int>G[maxn];
int dp[maxn][maxn];
int root = 0;
string S;
stringstream SS;
unordered_map<string, int>um;
int score[maxn], sz[maxn];
bool fa[maxn];
 
void add_edge(int from, int to)
{
	G[from].push_back(to);
}
 
void dfs1(int v)
{
	sz[v] = 1;
	if (!G[v].size())
		return;
	for (int i = 0; i < G[v].size(); i++)
	{
		int u = G[v][i];
		dfs1(u);
		sz[v] += sz[u];
	}
}
 
void dfs2(int v)
{
	dp[v][0] = 0;
	for (int i = 1; i <= M; i++)
		dp[v][i] = inf;
	for (int i = 0; i < G[v].size(); i++)
	{
		int u = G[v][i];
		dfs2(u);
		for (int j = sz[v]; j >= 0; j--)
		{
			for (int k = 0; k <= min(sz[u], j); k++)
				dp[v][j] = min(dp[v][j], dp[v][j - k] + dp[u][k]);
		}
	}
	if (v)
	{
		for (int i = 0; i <= sz[v]; i++)
			dp[v][i] = min(dp[v][i], score[v]);
	}
}
 
void solve()
{
	int ans = inf;
	dfs1(root);
	dfs2(root);
	cout << dp[0][M] << endl;
}
 
int main()
{
	IOS;
	char ch;
	int idx = 0;
	while (getline(cin, S) && S[0] != '#')
	{
		um.clear();
		memset(dp, 0x3f, sizeof(dp));
		memset(fa, 0, sizeof(fa));
		SS.clear(), SS.str(S);
		SS >> N >> M;
		for (int i = 0; i <= N; i++)
			G[i].clear();
		for (int i = 0; i < N; i++)
		{
			getline(cin, S);
			SS.clear(), SS.str(S);
			string country;
			int value;
			SS >> country >> value;
			if (um[country] == 0)
				um[country] = ++idx;
			score[um[country]] = value;
			string sub;
			while (SS >> sub)
			{
				if (um[sub] == 0)
					um[sub] = ++idx;
				add_edge(um[country], um[sub]);
				fa[um[sub]] = true;
			}
		}
		for (auto a : um)
		{
			if (!fa[a.second])
				add_edge(root, a.second);
		}
		solve();
	}
 
	return 0;
}