Биллион Миллион Тысяча

Лингвист Нодвик Натарус Даменхоф, известный как доктор Усоперант, создал искусственный язык Усоперант в 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 указывает количество слов в словаре экспоненциальных чисел.

Следующие N строк содержат слова из словаря. Каждая строка содержит слово w_i и целое число p_i (1 ≤ i ≤ N, 1 ≤ p_i ≤ 10), указывающее, что слово w_i выражает экспоненциальное число 10^pi на Усоперанте. Каждое w_i состоит из не более чем 100 букв.

Затем следует строка, содержащая выражение числа на Усоперанте. Выражение состоит из не более чем 200 букв.

Конец входных данных обозначается строкой, содержащей только одну цифру 0.

Выходные данные

Для каждого теста выведите строку, содержащую номер теста и длину самого короткого выражения, которое представляет то же число, что и данное выражение во входных данных.