Bright Bracelet

Time limit1sMemory limit128 MB

Summary
Arrange all octagons in a cycle so adjacent edges match in color, minimizing the total brightness at the joints.
Level

Hard8 of 10

Topics
Backtracking, Brute force, Implementation, Graph
Solved
No attempts yet

Problem

Bracelet 1

Bracelet 2

A bracelet is built from octagonal pieces, joining two opposite sides of each octagon to the octagons on either side. The sides of an octagon are colored, and different colors are labeled with different letters. A bracelet looks good only when the two touching sides of adjacent octagons have the same color. The pictures above show two bracelets that can be made. (The two ends are also fastened together.) Both bracelets use the same four octagons, only reordered and rotated. Octagons are never flipped over.

The darker the colors on the connecting sides, the better the bracelet sells. The brightness of each labeled color is a positive integer, and a larger value means brighter. Suppose the brightness of the colors is:

ABCDEFGH
7090105060302040

We compare two arrangements by adding the brightness of the touching color at every joint (including the joint that connects the two ends). Bracelet 1 has joint colors A, A, E, E, so its sum is 70 + 70 + 60 + 60 = 260. Bracelet 2 has C, C, G, E, so its sum is 10 + 10 + 20 + 60 = 100. Bracelet 2, with the smaller sum, is preferable. In fact Bracelet 2 gives the smallest value obtainable from any reordering and rotation of these four octagons.

Input

There are between 1 and 20 data sets, followed by a final line containing only 0.

Each data set starts with a line of nine space-separated integers. The first is nn, the number of octagons in the bracelet, with 4≤n≤114 \le n \le 11. The remaining eight are the brightness values for colors A through H, in order. Each brightness is positive and less than 256256.

The next nn lines each contain eight letters from A through H, giving the edge colors of one octagon in clockwise order. A color may appear any number of times within an octagon. Two different colors may have the same brightness, but that does not make them the same color.

Output

Print one line per data set. If no bracelet can be built using all of the octagons, print impossible. Otherwise print the minimum possible sum of brightness over the connections.

Note: trying every ordering and rotation individually is too slow to finish in time.

Examples3

  1. Example 1

    Input
    4 70 90 10 50 60 30 20 40
ACACACAC
ABCDEFGH
EEEEECCC
EECCAGGG
5 1 2 3 4 5 6 7 8
AAAABBBB
BBBBCCCC
CCCCDDDD
DDDDEEEE
EEEEAAAA
6 50 50 50 50 100 1 2 3
HHHHHHHH
BBBBCCCC
CDCDDDDD
DEDEEEEE
EFEFEFEF
FFFFFFFF
0
    Expected output
    100
15
impossible

  2. Example 2

    Input
    4 1 2 3 4 9 9 9 9
AAAABBBB
BBBBCCCC
CCCCDDDD
DDDDAAAA
0
    Expected output
    10

  3. Example 3

    Input
    4 5 1 1 1 1 1 1 1
AAAAAAAA
AAAAAAAA
AAAAAAAA
AAAAAAAA
0
    Expected output
    20