Billion Million Thousand

A linguist, Nodvic Natharus Damenhof (commonly called Dr. Usoperant), invented an artificial language Usoperant in 2007. The word usoperant means 'one which tires'. Damenhof’s goal was to create a complex and pedantic language that would remind many difficulties in universal communications. Talking in Usoperant, you should remember the importance of choosing your words in many conversations.

For example of the complexity, you may be confused by the way to say large numbers. Usoperant has some words that indicate exponential numbers in decimal, described as 10^p where p is a positive integer. In terms of English, those words might include thousand for 10^3 (1000), million for 10^6 (1000000), and undecillion for 10^36 (1000000000000000000000000000000000000).

You can concatinate those words to express larger numbers. When two words w_1 and w_2 mean numbers 10^p1 and 10^p2 respectively, a concatinated word w_1w_2 means 10^{p1+p2}. Using the above examples in English (actually the following examples are incorrect in English), you can say 10^9 by millionthousand, 10^12 by millionmillion and 10^39 by undecillionthousand. Note that there can be multiple different expressions for a certain number. For example, 10^9 can also be expressed by thousandthousandthousand. It is also possible to insert separators between the adjacent components like million-thousand and thousand-thousand-thousand.

In this problem, you are given a few of such words, their representing digits and an expression of a certain number in Usoperant. Your task is to write a program to calculate the length of the shortest expression which represents the same number as the given expression.

The expressions in the input do not contain any separators like millionthousand. In case of ambiguity, the expressions should be interpreted as the largest number among possibles. The resultant expressions should always contain separators like million-thousand, so we can distinguish, for example, x-x (a concatinated word of two x’s) and xx (just a single word). The separators should not be counted in the length.

Input

The input consists of multiple test cases. Each test case begins with a line including an integer N (1 ≤ N ≤ 100). The integer N indicates the number of words in the dictionary of exponential numbers.

The following N lines give the words in the dictionary. Each line contains a word w_i and an integer p_i (1 ≤ i ≤ N, 1 ≤ p_i ≤ 10), specifying that the word w_i expresses an exponential number 10^pi in Usoperant. Each w_i consists of at most 100 alphabetical letters.

Then a line which contains an expression of a number in Usoperant follows. The expression consists of at most 200 alphabetical letters.

The end of the input is indicated by a line which contains only a single 0.

Output

For each test case, print a line which contains the case number and the length of the shortest expression which represents the same number as the given expression in the input.