بنت در شرکت ایرانفون به عنوان یک برنامه نویس مشغول به کار است. رئیس ایرانفون هر سال به خوش اخلاق‌ترین کارمندانش جایزه بزرگی می‌دهد. بنت می‌خواهد امسال برنده این جایزه باشد. برای انتخاب برنده‌ها، ابتدا چند نفر کاندیدا می‌شوند. سپس رئیس نظر همه کارمندانی که کاندیدا نشده‌اند را می‌پرسد و به تمام کاندیداهایی که حداقل $m$ رای آورده باشند جایزه می‌دهد.

بنت، می‌خواهد با خریدن رأی بعضی از همکارانش، مطمئن شود که برنده خواهد بود. هر فرد قیمت خاصی برای رأیش قائل است، همچنین بعضی از افراد رئیسی دارند. اگر بنت رأی کسی را بخرد، تمام کسانی که به صورت مستقیم یا غیر مستقیم زیر‌دست او هستند نیز به بنت رأی خواهند داد.

حال او از شما درخواست کرده است که برنامه‌ای بنویسید که به او بگوید او باید حداقل چه مقدار برای بردن این جایزه خرچ کند.

در ورودی چند سناریو آمده است. هر سناریو با خطی شامل دو عدد $n$ (تعداد افرادی که رأی می‌دهند) و m آغاز شده است. ($ 1 ⇐ n ⇐ 200, 0 ⇐ m ⇐ n $)

در $n$ خط بعد در هر خط ابتدا نام فرد $i$ام (رشته‌ای به طول حداکثر ۱۰۰ حرف) و سپس میزان پولی که بنت باید به او بدهد تا رأی او را بخرد آمده و بعد از آن نام تمام کارمندانی آمده است که رئیشان فرد $i$ام است.

خط آخر ورودی تنها شامل یک کاراکتر # است.

برای هر سناریو،‌ در یک خط کمینه مقدار هزینه‌ای را که بنت باید خرج کند تا حداقل $m$ نفر به او رأی دهند را چاپ کنید.

• محدودیت زمان: ۱۰ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت