## 1064: 2010欧洲西南分区赛：Assembly line

时间限制: 1 Sec 内存限制: 128 MB提交: 0 解决: 0

[提交][状态][讨论版]

## 题目描述

## 输入

The input consists of several test cases. Each test case begins with a line containing a natural number k

(1 <= k <= 26), followed by a line with k symbols (characters in [a-z]) separated by spaces. The following k

lines contain the assembly table: the i-th line has k pairs of the form time-result, where time is an integer

between 0 and 1 000 000 inclusive, and result a symbol belonging to the preceding set. The j-th pair in the

i-th line represents the time to compose pieces of types represented by the i-th and j-th symbols, along with

the type of the resulting piece. After the table, a line with an integer n indicates the number of lines that

follow, each line being a string of at most 200 symbols. Each of these lines is a sequence of components that

need to be assembled together in the right order.

The input will nish with a line containing 0, which should not be processed.

## 输出

For each test case, print n lines, each with an integer time and a symbol result in the format time-result.

Each line represents the minimum time and the type of the resulting piece for the corresponding case in the

input. In case of a tie among several possible results with the same minimum time, choose from among those

the piece whose type letter appears rst in the line that contained the k symbols at the beginning of the test

case. (For example, if that line was a c b and both c and b can be obtained with minimum cost 5, print 5-c).

There must be an empty line between the output of di erent test cases.

## 样例输入

```
2
a b
3-b 5-b
6-a 2-b
2
aba
bba
2
m e
5-e 4-m
3-e 4-m
1
eme
0
```

## 样例输出

```
9-b
8-a
7-m
```