Pulu Göstər Mənə#4273
Frank Marks böyük bir şirkətin Biznes Ofisində çalışır. Onun şirkəti dünya üzrə müştərilərlə işləyir və müxtəlif valyutalarla əməliyyatlar aparır. İşçilər tez-tez müəyyən məbləğdə pul, məsələn, 100 ABŞ dolları və ya 452 Avro üçün Biznes Ofisinə müraciət edirlər. Əgər Frankın əlində kifayət qədər nağd pul varsa, o, tələb olunan məbləği dəqiq verir; əks halda, o, başqa bir valyuta ilə əvəz edir. Bu, bəzən çətin olur, çünki onun seçim edə biləcəyi çoxlu fərqli valyutalar var və o, mümkün qədər ilkin tələbinə yaxınlaşmağa çalışır, lakin tələb olunan məbləğdən aşağı düşmədən (o, tələb olunan dəyəri ən azı təmin etməlidir). Məsələn, tutaq ki, Frankın altı fərqli valyutası var - A, B, C, D, E və F - və o, aşağıdakı məzənnələri bilir:
23 A = 17 B
16 C = 29 E
5 B = 14 E
1 D = 7 F
Əgər 100 A üçün bir tələb gəlirsə, lakin Frankın əlində 100 A yoxdursa, o, ya 74 B (təxminən 100.12 A ekvivalent), ya da 115 C (təxminən 100.72 A ekvivalent) və ya 207 E (təxminən 100.02 A ekvivalent) ilə əvəz edə bilər. Beləliklə, onun üçün mövcud olan ən yaxşı yaxınlaşma 207 E-dir. Qeyd edək ki, Frankın A və D valyutaları arasında və ya A və F valyutaları arasında əlaqə qurmaq üçün kifayət qədər məlumatı yoxdur. Həmçinin, Frankın hər hansı bir valyutanın ən çox 100000 vahidi var, buna görə də o, E valyutası ilə 64000 A tələbinə cavab verə bilməz və 73078 C istifadə etməlidir.
Tələb olunan valyuta tamamilə tükəndikdə istifadə ediləcək ideal əvəz valyutanı müəyyənləşdirmək vaxt aparır, buna görə də Frank bu hesablamaları onun üçün edəcək bir proqram istəyir.
Hər bir test halı mübadilə məzənnələrinin sayını göstərən müsbət tam ədəd n ilə başlayır. Növbəti n sətir aşağıdakı formada olacaq
val_1 name_1 = val_2 name_2
burada name_1 və name_2 iki fərqli valyutanın adlarıdır və val_1 və val_2 iki valyuta arasındakı nisbəti göstərən müsbət tam ədədlərdir və 30-dan çox olmayacaq. 8-dən çox olmayan fərqli valyuta adları olacaq və hər hansı iki valyuta bir dəfə cütləşdiriləcək. Valyuta adları on hərfə qədər olan əlifba simvollarından ibarət olacaq. Girişdə heç bir uyğunsuzluq olmayacaq (məsələn, 1A = 2B, 1B = 2C və 1C = 2A). Bu n sətirdən sonra aşağıdakı formada bir sətir olacaq
val name
bu, tələb olunan məbləği (müsbət tam ədəd 100000-dən çox olmayacaq) və valyutanın adını göstərir. Son test halını izləyən bir sətir 0 olacaq.
Hər bir test halı üçün, Frankın tələb olunan valyutadan heç birinin olmadığını, lakin bütün digər valyutaların tam ehtiyatda olduğunu nəzərə alaraq, tələb olunan dəyərin altına düşmədən ən yaxın yaxınlaşmanı çap edin. Hər bir problem nümunəsi üçün unikal cavab olacaq.
Nümunə 1