Address Matching

Researcher Uuno ran a survey among students, asking each of them to write down their email address. Many of the handwritten addresses turned out to be very hard to read, so Uuno asked the class teacher for a separate list of every student's address in order to cross-check. He now wants to pair up the two lists so that all three of the following conditions hold:

1. every address in the first list is matched to exactly one address in the second list,
2. no address in the second list is matched to more than one address in the first list,
3. among all pairings that satisfy conditions 1 and 2, the total difference of the matched pairs is minimized.

The difference between two addresses is defined as follows. Any address can be turned into another one by inserting, deleting, and replacing characters. Each operation has a fixed cost: deleting a single character costs $c_D$, inserting a single character costs $c_A$, and replacing one character with another costs a value given in the input. The difference of two addresses is the minimum total cost of transforming the second address into the first.

Find a pairing that satisfies the three conditions. If several pairings achieve the minimum total difference, output the lexicographically smallest one.

• Line 1: an integer $N$ ($1 \le N \le 20$) — the number of addresses collected from the students.
• Line 2: the $N$ student email addresses, separated by spaces.
• Line 3: an integer $M$ ($N \le M \le 20$) — the number of addresses received from the teacher.
• Line 4: the $M$ teacher addresses, separated by spaces.
• Line 5: two integers $c_D$ and $c_A$ ($0 \le c_D, c_A \le 10^6$) — the cost of deleting and of inserting a single character.
• Line 6: the number $K$ of distinct characters used in the addresses ($1 \le K \le 60$).
• Line 7: exactly $K$ characters given as a single string with no separators.
• The next $K$ lines: a $K \times K$ matrix with $K$ integers per line. The value $c_{i,j}$ ($0 \le c_{i,j} \le 10^6$) in row $i$, column $j$ is the cost of replacing the $i$-th character on line 7 with the $j$-th one, and $c_{i,i} = 0$.

Every address consists of at most 100 characters, and every character occurring in any address is one of the $K$ characters listed on line 7.

• Line 1: the minimum total difference over all valid pairings.
• Line 2: $N$ space-separated integers $v_1, \dots, v_N$, where $v_i$ (1-indexed) is the position in the teacher's list matched to the $i$-th student address. If several pairings achieve the minimum total difference, output the one whose sequence $(v_1, v_2, \dots, v_N)$ is lexicographically smallest.