Мільярд Мільйон Тисяча
Лінгвіст Нодвік Натарус Даменгоф, відомий як доктор Усоперант, створив штучну мову Усоперант у 2007 році. Назва усоперант означає 'той, що втомлює'. Його метою було розробити складну та педантичну мову, яка б нагадувала про численні труднощі в універсальних комунікаціях. Спілкуючись на Усоперанті, ви повинні пам'ятати про важливість вибору слів у багатьох розмовах.
Наприклад, однією з особливостей є спосіб вираження великих чисел. Усоперант має певні слова, що позначають експоненційні числа в десятковій системі, описані як 10^p, де p — додатне ціле число. У термінах англійської, ці слова можуть включати тисяча для 10^3 (1000), мільйон для 10^6 (1000000) та ундекільйон для 10^36 (1000000000000000000000000000000000000).
Ви можете об'єднувати ці слова, щоб виразити більші числа. Якщо два слова w_1 та w_2 означають числа 10^p1 та 10^p2 відповідно, об'єднане слово w_1w_2 означає 10^{p1+p2}. Використовуючи наведені вище приклади англійською (насправді наступні приклади є неправильними в англійській), ви можете сказати 10^9 як мільйонтисяча, 10^12 як мільйонмільйон та 10^39 як ундекільйонтисяча. Зверніть увагу, що для певного числа можуть існувати кілька різних виразів. Наприклад, 10^9 також може бути виражено як тисячатисячатисяча. Також можливо вставляти роздільники між сусідніми компонентами, як мільйон-тисяча та тисяча-тисяча-тисяча.
У цій задачі вам надано кілька таких слів, їхні відповідні цифри та вираз певного числа на Усоперанті. Ваше завдання — написати програму, яка обчислює довжину найкоротшого виразу, що представляє те саме число, що й даний вираз.
Вирази у вхідних даних не містять жодних роздільників, як мільйонтисяча. У разі неоднозначності вирази слід інтерпретувати як найбільше число серед можливих. Результуючі вирази завжди повинні містити роздільники, як мільйон-тисяча, щоб ми могли розрізнити, наприклад, x-x (об'єднане слово з двох x) та xx (просто одне слово). Роздільники не повинні враховуватися в довжині.
Вхідні дані
Вхід складається з кількох тестових випадків. Кожен тестовий випадок починається з рядка, що містить ціле число N (1 ≤ N ≤ 100). Це число вказує на кількість слів у словнику експоненційних чисел.
Наступні N рядків містять слова у словнику. Кожен рядок містить слово w_i та ціле число p_i (1 ≤ i ≤ N, 1 ≤ p_i ≤ 10), що вказує, що слово w_i виражає експоненційне число 10^pi на Усоперанті. Кожне w_i складається з не більше ніж 100 алфавітних літер.
Потім слідує рядок, що містить вираз числа на Усоперанті. Вираз складається з не більше ніж 200 алфавітних літер.
Кінець введення позначається рядком, що містить лише одну цифру 0.
Вихідні дані
Для кожного тестового випадку виведіть рядок, що містить номер випадку та довжину найкоротшого виразу, що представляє те саме число, що й даний вираз у вхідних даних.