Покажи мені гроші
Френк Маркс працює в Бізнес-офісі великої компанії. Його компанія має клієнтів по всьому світу і повинна працювати з багатьма різними валютами. Співробітники часто звертаються до Бізнес-офісу з проханнями про певні суми грошей, наприклад, 100 американських доларів або 452 євро. Якщо у Френка є потрібна готівка, він видає співробітнику саме те, що потрібно; якщо ж у нього недостатньо запитуваної валюти, він замінює її на іншу. Це іноді буває складно, оскільки у нього може бути багато різних валют на вибір, і він хотів би вибрати ту, яка дозволяє йому максимально наблизитися до початкової заявки, не зменшуючи її (він повинен надати принаймні запитувану вартість). Наприклад, припустимо, що у Френка є шість різних валют - A, B, C, D, E та F - і він знає про такі курси обміну:
23 A = 17 B
16 C = 29 E
5 B = 14 E
1 D = 7 F
Якщо надійде заявка на 100 A, але у Френка менше ніж 100 A в наявності, він може замінити на 74 B (еквівалентно приблизно 100.12 A), 115 C (еквівалентно приблизно 100.72 A) або 207 E (еквівалентно приблизно 100.02 A). Таким чином, найкраще наближення, яке він може запропонувати, це 207 E. Зверніть увагу, що у Френка недостатньо інформації, щоб знайти співвідношення між валютами A та D або валютами A та F. Також, у Френка є максимум 100000 одиниць будь-якої валюти в наявності, тому він не міг би задовольнити запит на 64000 A за допомогою валюти E і повинен був би використовувати 73078 C замість цього.
Визначення ідеальної заміни валюти, коли у нього повністю закінчилася запитувана валюта, займає багато часу, тому Френк хотів би мати програму, яка робитиме розрахунки за нього.
Вхідні дані
Кожен тестовий випадок починається з додатного цілого числа n, що вказує кількість курсів обміну. Наступні n рядків будуть у формі
val_1 name_1 = val_2 name_2
де name_1 та name_2 - це назви двох різних валют, а val_1 та val_2 - додатні цілі числа ≤ 30, що вказують на співвідношення між двома валютами. Не буде більше ніж 8 різних назв валют, і будь-які дві валюти будуть поєднані разом не більше одного разу. Назви валют складатимуться з до десяти алфавітних символів. У вхідних даних не буде суперечностей (таких як 1A = 2B, 1B = 2C та 1C = 2A). Після цих n рядків буде один рядок у формі
val name
який вказує на кількість (додатне ціле число, що не перевищує 100000) та назву запитуваної валюти. Рядок, що містить 0, буде слідувати за останнім тестовим випадком.
Вихідні дані
Для кожного тестового випадку надрукуйте номер випадку та найближче наближення без зменшення запитуваної вартості, припускаючи, що у Френка немає жодної з запитуваної валюти, але він повністю забезпечений усіма іншими валютами. Для кожного випадку буде унікальна відповідь.