Bright Bracelet

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:

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.

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 $n$, the number of octagons in the bracelet, with $4 \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 $256$.

The next $n$ 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.

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.