Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 2574
Elaborate Short Messages

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Background

Now most mobile phones support T9. In T9 text input, if you want to enter "hello", you simply press keys 4, 3, 5, 5, and 6 once(Please see Figure 1). But before T9 text input, it is quite cumbersome to send message. For example, if you want to type "hello", you had to press key 4 twice, key 3 twice, key 5 three times, again key 5 three times, and finally key 6 three times. This procedure is very tedious and keeps many people from using the Short Message Service, here we just call it "STUPID" input text.

There is another method called "SMART" input text to improve the speed of editing short message in mobile. Please see Figure 2, if you type 'h', 'e' and 'i' will appear in the "Next character predict area"(we suppose in this case, "hello" and "hi" are in the word dictionary of mobile), then press key 1 once (to switch to the predict-mode), figure 3 will appear instead of figure 2. Then you can press key 1 again to type 'e'. Then only 'l' appears in "Next character predicted area". As we all know, the letter in "Next character predicted area" is used to predict user's next input. We should pay attention that, when there's no input, there's also some characters in "Next character predict area".

In this problem, we suppose the size of "Next character predict area" is 5, which is to say, 5 characters could show in one page, if you want to turn one page down, you have to press "page down" key once, as the same reason, if you want to turn two pages down, you have to press "page down" key twice. Whether a character is in page 1 or page 2 of "Next character predict area", it depends on this character's probability. If some combinations have the same probability, your program should let the first character in alphabetic order appear in the page first. Also, you needn't to press any other key to change "STUPID" input text method to "SMART" input text method.

Problem

Write a program to find the smallest press-key number using either "STUPID" or "SMART" method for every character in the short message. For example, if you want to send this message: "hello". If you choose "STUPID" method for every character in the short message, the press-key number is 2+2+3+3+3 = 13, while you choose "SMART" method, the press-key number is 2+2+2+2+2 = 10(we suppose only "hello" is in the word dictionary of mobile). Another example to show this program, if the message is "feati", the word dictionary is "feather" and "till", then the minimum press-key number is 2(SMART)+2(SMART)+1(STUPID)+1(STUPID)+3(STUPID)=9. The press-key number of all the symbols except letters, such as whitespace, comma and digit is 1.

Input

The first line contains the number of scenarios. Each scenario begins with a line containing the number w of distinct words in the word dictionary (0 <= w<= 10000). These words are in the next w lines. Every line starts with the word which is a sequence of lowercase letters without whitespace, followed by a space and an integer p, 0 <= p <= 100, representing the probability of that word. No word will contain more than 100 letters. Then next line contains the number n of short messages which need to be typed. (1 <= n <= 1000) The short messages (all the letters are lowercase) are in the next n lines.

Output

The output for each scenario begins with a line containing "Scenario #i:", where i is the number of the scenario starting at 1. For every short message of the scenario, print the mininum press-key number. Print an additional blank line at the end of each scenario.

Sample Input

2

2
hello 5
hi 10
1
hello

2
feather 5
to 4
2
feati
3?. #

Sample Output

Scenario #1:
10

Scenario #2:
9
5



Author: GU, Pingping
Source: ZOJ Monthly, October 2005
Submit    Status