A linguist, Nodvic Natharus Damenhof (commonly called \textit{Dr. Usoperant}), invented an artificial language Usoperant in \textbf{2007}. The word \textit{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 \textbf{10^p} where \textbf{p} is a positive integer. In terms of English, those words might include \textit{thousand} for \textbf{10^3} (\textbf{1000}), \textit{million} for \textbf{10^6} (\textbf{1000000}), and \textit{undecillion} for \textbf{10^36} (\textbf{1000000000000000000000000000000000000}). You can concatinate those words to express larger numbers. When two words \textbf{w_1} and \textbf{w_2} mean numbers \textbf{10^p1} and \textbf{10^p2} respectively, a concatinated word \textbf{w_1w_2} means \textbf{10^\{p1+p2\}}. Using the above examples in English (actually the following examples are incorrect in English), you can say \textbf{10^9} by \textit{millionthousand}, \textbf{10^12} by \textit{millionmillion} and \textbf{10^39} by \textit{undecillionthousand}. Note that there can be multiple different expressions for a certain number. For example, \textbf{10^9} can also be expressed by \textit{thousandthousandthousand}. It is also possible to insert separators between the adjacent components like \textit{million-thousand} and \textit{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 \textit{millionthousand}. In case of ambiguity, the expressions should be interpreted as the largest number among possibles. The resultant expressions should always contain separators like \textit{million-thousand}, so we can distinguish, for example, \textbf{x-x} (a concatinated word of two \textbf{x}’s) and \textbf{xx} (just a single word). The separators should not be counted in the length. \InputFile The input consists of multiple test cases. Each test case begins with a line including an integer \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{100}). The integer \textbf{N} indicates the number of words in the dictionary of exponential numbers. The following \textbf{N} lines give the words in the dictionary. Each line contains a word \textbf{w_i} and an integer \textbf{p_i} (\textbf{1} ≤ \textbf{i} ≤ \textbf{N}, \textbf{1} ≤ \textbf{p_i} ≤ \textbf{10}), specifying that the word \textbf{w_i} expresses an exponential number \textbf{10^pi} in Usoperant. Each \textbf{w_i} consists of at most \textbf{100} alphabetical letters. Then a line which contains an expression of a number in Usoperant follows. The expression consists of at most \textbf{200} alphabetical letters. The end of the input is indicated by a line which contains only a single \textbf{0}. \OutputFile 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.