Конвеєрна лінія
Остання працівниця на виробничій лінії заводу Automated Composed Machinery занепокоєна. Вона знає, що її робота під загрозою, якщо її продуктивність не покращиться. Її завдання полягає в збиранні набору деталей у певній послідовності, але час, необхідний для збирання деталей a і b, а потім c, може відрізнятися від часу, потрібного для збирання деталей b і c, а потім додавання a до отриманого компонента. Лише дві послідовні деталі можуть бути зібрані одночасно, і після збирання вони поводяться як нова деталь з точки зору часу, необхідного для подальшого збирання.
Щоб допомогти їй, вам потрібно знайти оптимальний спосіб зібрати всі компоненти. Вхідними даними для вашої програми буде набір символів, що представляють (типи) деталей, і так звана таблиця збирання, яка вказує час, необхідний для їх збирання, а також тип отриманого компонента. Наприклад, ми можемо мати два символи {a, b}, і таку таблицю:
Це означає, наприклад, що дві деталі типу a і a можуть бути зібрані за 3 хвилини, і результатом є компонент типу b, так що час, необхідний для його збирання з іншою деталлю, скажімо, типу a, становить 6 хвилин, і так далі. Зверніть увагу, що таблиця не симетрична, тобто збирання b і a може зайняти більше часу, ніж a і b.
Для послідовності компонентів, позначеної aba, можливі два рішення:
(ab)a = ba = a з часом time(ab) + time(ba) = 5 + 6 = 11.
a(ba) = aa = b з часом time(ba) + time(aa) = 6 + 3 = 9.
Отже, результатом у цьому випадку буде деталь типу b за 9 хвилин (позначено 9-b).
Вхідні дані
Вхідні дані складаються з кількох тестових випадків. Кожен тестовий випадок починається з рядка, що містить натуральне число k (1 ≤ k ≤ 26), за яким слідує рядок з k символами (символи в [a-z]), розділеними пробілами. Наступні k рядків містять таблицю збирання: i-й рядок має kpар пар виду час- результат, де час — це ціле число від 0 до 1 000 000 включно, а результат — символ, що належить до попереднього набору. j-та пара в i-му рядку представляє час для складання деталей типів, представлених i-м і j-м символами, разом з типом отриманої деталі. Після таблиці йде рядок з цілим числом n, що вказує кількість рядків, які слідують, кожен рядок є рядком з не більше ніж 200 символів. Кожен з цих рядків є послідовністю компонентів, які потрібно зібрати разом у правильному порядку.
Вхідні дані закінчуються рядком, що містить '0', який не слід обробляти.
Вихідні дані
Для кожного тестового випадку виведіть n рядків, кожен з яких містить ціле число часу і символ результату у форматі час- результат. Кожен рядок представляє мінімальний час і тип отриманої деталі для відповідного випадку у вхідних даних. У разі рівності кількох можливих результатів з однаковим мінімальним часом, виберіть з них деталь, чия літера типу з'являється першою в рядку, що містив kсимволи на початку тестового випадку. (Наприклад, якщо цей рядок був a c b і як c, так і b можуть бути отримані з мінімальною вартістю 5, виведіть 5-c).
Між виводом різних тестових випадків повинен бути порожній рядок.