//-----------------------------------------------------------------------------
//解法：
//  依存関係の制約に注意して、普通のKnapsack問題の擬多項式時間アルゴリズム。
//   O( costMax * numItem ) 時間。
//-----------------------------------------------------------------------------

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <cassert>
using namespace std;

// 依存関係のツリー構造
struct node
{
	vector<string> child;
	int            cost;
	int            happy;
	node() : child(), cost(0), happy(0) {}
};
typedef map<string,node> tree;

// 解候補の集合
typedef map<int,int>         CostHappyTable;
typedef map<int,int>::iterator       cht_it;

// ツリーの各ノードを訪問
//   invariant: \exist h. (0,h) \in tbl
//   invariant: tbl, sub は(Cost,Happiness) の狭義双単調増加列
void rec( tree& t, const string& item, int costMax, map<int,int>& tbl )
{
	node& n = t[item];

	// itemを買う場合に最適な CostHappyTable を計算
	CostHappyTable sub;
	for(cht_it i=tbl.begin(); i!=tbl.end(); ++i)
		if( i->first+n.cost <= costMax )
			sub[i->first+n.cost] = i->second+n.happy;
	for(int i=0; i!=n.child.size(); ++i)
		rec( t, n.child[i], costMax, sub );

	// itemを買わない場合とマージ
	for(cht_it i=sub.begin(); i!=sub.end(); ++i)
	{
		// le <= i < ub
		cht_it ub = tbl.upper_bound( i->first );
		cht_it le = ub; --le;

		// invariantを保ちつつ挿入
		if( le->second < i->second )
		{
			tbl[i->first] = i->second;
			while( ub != tbl.end() )
				if( i->second >= ub->second )
				{
					cht_it ub2=ub; ++ub;
					tbl.erase(ub2);
				}
				else
					break;
		}
	}
}

pair<int,int> solve( tree& t, int cash )
{
	CostHappyTable tbl;
	tbl[0] = 0;
	rec( t, "&", cash, tbl );
	return *tbl.rbegin();
}

int main()
{
	string name;
	int    cash;

	while( cin>>name>>cash, name!="#" )
	{
		assert( 0<=cash && cash<=1024 );
		tree t;

		// 依存関係読み込み
		for(;;)
		{
			string item, dep;
			int cost, happiness;
			if( cin>>item, item=="%" )
				break;
			cin >> dep >> cost >> happiness;
			assert( 0<=cost && cost<=1024 );
			assert( 0<=happiness && happiness<=100000 );

			t[dep].child.push_back(item);
			t[item].cost  = cost;
			t[item].happy = happiness;
		}
		void validate( tree& t );
		validate(t);

		// 解く
		pair<int,int> ans = solve( t, cash );

		// 出力
		static bool is_first = true;
		if( is_first ) is_first=false; else cout<<endl;
		cout << name << endl;
		cout << "Max happiness:" << ans.second << endl;
		cout << "Cost:"          << ans.first  << endl;
	}
}

// 入力検証
void validate( tree& t )
{
	struct depth_checker {
		static int rec( tree& t, const string& item ) {
			vector<string>& ch = t[item].child;
			int Max = 0;
			for(int i=0; i!=ch.size(); ++i) {
				int a = 1+rec(t,ch[i]);
				Max = Max>a ? Max : a;
			}
			return Max;
		}
	};

	for(tree::iterator it=t.begin(); it!=t.end(); ++it)
		assert( it->second.child.size() <= 32 );
	assert( depth_checker::rec(t,"&") < 5 );
}


/** // 遅い上に間違ってたぽい…？
void aggregate( CostHappyTable& a, CostHappyTable& b, int cLimit )
{
	CostHappyTable g;
	for(cht_it it=a.begin(); it!=a.end(); ++it)
	for(cht_it jt=b.begin(); jt!=b.end(); ++jt)
	{
		int f = it->first  + jt->first;
		int s = it->second + jt->second;
		if( f > cLimit )
			break;
		else if( g[f] < s ) {
			g[f] = s;
			for(;;) {
				map<int,int>::iterator kt = g.upper_bound(f);
				if( kt==g.end() || kt->second > s)
					break;
				g.erase(kt);
			}
		}
	}
	a = g;
}

void rec( tree& t, const string& item, int costMax, CostHappyTable& gt )
{
	gt.clear();

	node& n = t[item];
	if( costMax >= n.cost ) // このアイテムを買う場合
	{
		gt[n.cost] = n.happy;
		for(int i=0; i!=n.child.size(); ++i)
		{
			CostHappyTable sub_gt; // 各childアイテムを最適に買ってみる
			rec( t, n.child[i], costMax-n.cost, sub_gt );
			aggregate( gt, sub_gt, costMax ); // 集計
		}
	}
	gt[0]; // 買わない場合
}
**/