Покажи мені гроші#4273

Покажи мені гроші

1 секунда

64 мегабайти

Легка

Френк Маркс працює в Бізнес-офісі великої компанії. Його компанія має клієнтів по всьому світу і повинна працювати з багатьма різними валютами. Співробітники часто звертаються до Бізнес-офісу з проханнями про певні суми грошей, наприклад, $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}$ \text{val}_1 $name_{1}$ \text{name}_1 = $val_{2}$ \text{val}_2 $name_{2}$ \text{name}_2

де $name_{1}$ \text{name}_1 та $name_{2}$ \text{name}_2 - це назви двох різних валют, а $val_{1}$ \text{val}_1 та $val_{2}$ \text{val}_2 - додатні цілі числа $\leq 30$ , що вказують на співвідношення між двома валютами. Не буде більше ніж $8$ різних назв валют, і будь-які дві валюти будуть поєднані разом не більше одного разу. Назви валют складатимуться з до десяти алфавітних символів. У вхідних даних не буде суперечностей (таких як 1A = 2B, 1B = 2C та 1C = 2A). Після цих $n$ рядків буде один рядок у формі

$val$ $name$

який вказує на кількість (додатне ціле число, що не перевищує $100000$ ) та назву запитуваної валюти. Рядок, що містить $0$ , буде слідувати за останнім тестовим випадком.

Вихідні дані

Для кожного тестового випадку надрукуйте номер випадку та найближче наближення без зменшення запитуваної вартості, припускаючи, що у Френка немає жодної з запитуваної валюти, але він повністю забезпечений усіма іншими валютами. Для кожного випадку буде унікальна відповідь.

Приклади

Приклад 1