D :: Wiring Company

Time Limit: 10 Seconds    Memory Limit: 65536 KB

شما صاحب شرکت سیم کوچک هستید اما چون سرمایه­ی کافی برای شروع  کسب و کار خود ندارید از ابزارهایی استفاده می کنید که از انبار قدیمی­ای که آن را هم خریده­اید، پیدا کرده­اید.  در میان یافته­هایتان یک قرقره  سیم و تعدادی زیادی متصل کننده می­باشد. می­خواهید بفهمید که آیا مقداری کافی سیم در اختیار دارید تا تمام خانه­های شهر را به هم متصل کنید یا نه! نقشه­ی شهر شامل تمام مسیرهایی که ممکن است شما از آن ها برای سیم کشی استفاده کنید، را در اختیار دارید. شما باید کمترین طول سیمی را که لازم دارید تا تمام خانه­های شهر را به هم وصل کنید، پیدا کنید.

Input

فقط یک شهر به عنوان تست به شما  داده می­شود.

خط اول طول سیم موجود در قرقره است که به عنوان عدد حقیقی داده می­شود.

خط دوم شامل تعداد خانه­ها(N) می­باشد.

در N  خط بعدی نام صاحبان هر خانه می­آید. هر نام حداکثر ۲۰ کاراکتر شامل حروف کوچک و بزرگ انگلیسی و اعداد دارد و شامل فاصله و علائم نگارشی نمی­باشد.

خط بعدی عدد M  است که تعداد مسیرها می­باشد.

M خط بعدی به این شکل هستند که ابتدا نام دو فرد (متفاوت) از افراد صاحب خانه که بالاتر داده شده است، آورده می شود و سپس طول این مسیر که عدد حقیقی مثبتی ست داده می­شود. بین هر دو خانه­ هم حداکثر یک مسیر وجود دارد.

Output

خروجی تنها شامل یک خط  می­باشد. اگر مقدار سیم کافی برای سیم کشی تمام خانه­ها وجود دارد خروجی Not enough cable و در غیر این صورت خروجی Need X miles of cable چاپ می­شود که X  مقدار سیم لازم برای سیم کشی است و به نزدیک ترین دهم مایل گرد شده است.(0.1)

Sample Input

100.0
4
Jones
Smiths
Howards
Wangs
5
Jones Smiths 2.0
Jones Howards 4.2
Jones Wangs 6.7
Howards Wangs 4.0
Smiths Wangs 10.0

Sample Output

Need 10.2 miles of cable

Submit