Billion Million Thousand

언어학자 Nodvic Natharus Damenhof(흔히 Dr. Usoperant라고 불린다)는 2007년에 인공어 Usoperant를 만들었다. usoperant라는 단어는 '지치게 하는 것'을 뜻한다. Damenhof의 목표는 범세계적 의사소통에서 마주치는 여러 어려움을 떠올리게 하는, 복잡하고 현학적인 언어를 만드는 것이었다. Usoperant로 말할 때는 많은 대화에서 단어 선택이 얼마나 중요한지 기억해야 한다.

복잡함의 한 예로, 큰 수를 말하는 방식에 혼란을 겪을 수 있다. Usoperant에는 십진법에서 지수적 수를 나타내는 단어들이 있고, 이는 10p로 표현되며 p는 양의 정수다. 영어로 치면 이런 단어에는 103(1,000)을 뜻하는 thousand, 106(1,000,000)을 뜻하는 million, 1036(1,000,000,000,000,000,000,000,000,000,000,000,000)을 뜻하는 undecillion 등이 있다.

이런 단어들을 이어 붙여 더 큰 수를 표현할 수 있다. 두 단어 w1과 w2가 각각 10p1과 10p2를 뜻할 때, 이어 붙인 단어 w1w2는 10p1+p2를 뜻한다. 위의 영어 예를 쓰면(사실 다음 예들은 영어로는 틀린 표현이다) 109를 millionthousand로, 1012를 millionmillion으로, 1039를 undecillionthousand로 말할 수 있다. 어떤 수에 대해 서로 다른 여러 표현이 있을 수 있다는 점에 유의하라. 예를 들어 109는 thousandthousandthousand로도 표현할 수 있다. million-thousand나 thousand-thousand-thousand처럼 인접한 구성 요소 사이에 구분 기호를 넣는 것도 가능하다.

이 문제에서는 이런 단어 몇 개와 그 단어가 나타내는 지수, 그리고 Usoperant로 표현된 어떤 수가 주어진다. 주어진 표현과 같은 수를 나타내는 가장 짧은 표현의 길이를 계산하는 프로그램을 작성하라.

입력에 주어지는 표현에는 millionthousand처럼 구분 기호가 들어 있지 않다. 모호한 경우 표현은 가능한 것 중 가장 큰 수로 해석해야 한다. 결과로 나오는 표현에는 항상 million-thousand처럼 구분 기호가 들어가므로, 예를 들어 x-x(x 두 개를 이어 붙인 단어)와 xx(단일 단어)를 구별할 수 있다. 구분 기호는 길이에 세지 않는다.

입력은 여러 테스트 케이스로 이루어진다. 각 테스트 케이스는 정수 N(1 ≤ N ≤ 100)이 있는 줄로 시작한다. 정수 N은 지수 단어 사전에 있는 단어의 수다.

다음 N개의 줄은 사전에 있는 단어를 준다. 각 줄에는 단어 wi와 정수 pi(1 ≤ i ≤ N, 1 ≤ pi ≤ 10)가 있고, 단어 wi가 Usoperant에서 지수적 수 10pi를 나타낸다는 것을 뜻한다. 각 wi는 알파벳 문자 100개 이하로 이루어진다.

그다음 줄에는 Usoperant로 표현된 어떤 수의 표현이 온다. 이 표현은 알파벳 문자 200개 이하로 이루어진다.

입력의 끝은 0만 있는 줄로 나타난다.

각 테스트 케이스마다 케이스 번호와, 입력의 표현과 같은 수를 나타내는 가장 짧은 표현의 길이를 한 줄에 출력한다.

네 번째 케이스에서 단어 abcdefgh는 abcd-efgh(103을 나타낸다)와 abcde-fgh(1010을 나타낸다)로 나눌 수 있고, 문제에 설명한 규칙에 따라 이 단어는 1010으로 해석해야 한다. 이 수는 yy로 표현할 수 있으므로 가장 짧은 표현의 길이는 2다(예제 출력과 같다). y-y(1016을 나타낸다)가 존재하는 것은 문제가 되지 않는다. 항상 구분 기호를 쓰기만 하면 yy와 y-y를 구별할 수 있기 때문이다.