本题没有可用的提交语言。

问题描述

手镯1 手镯2 手镯可以由一组八角形部件制成，每个八角形的两个对边分别与相邻的两个八角形相连。八角形边缘的颜色各不相同，不同颜色用不同的字母在图中标注。手镯只有在相邻两个八角形的连接边颜色相同时才显得美观。上图展示了两种可能的手镯样式（两端也需连接）。这两种手镯可以由相同的四个八角形通过重新排列和旋转得到（假设八角形不会被翻转）。

更畅销的手镯通常是连接边颜色较深的手镯。每种字母颜色的亮度是一个正整数，数值越大表示越亮。假设标注颜色的亮度如下：

我们可以通过计算每个连接处（包括两端的连接）颜色的亮度之和来比较这两种八角形排列的优劣。对于手镯1，颜色A、A、E、E的亮度之和为$70 + 70 + 60 + 60 = 260$。对于手镯2，颜色C、C、G、E的亮度之和为$10 + 10 + 20 + 60 = 100$。手镯2更优，因为其总和更小。实际上，手镯2是所有可能的八角形排列和旋转中结果最好的。

输入格式

输入包含1到20个数据集，最后一行仅包含一个0。每个数据集的第一行包含9个空格分隔的整数。第一个整数$n$表示组成手镯的八角形数量，$4 \leq n \leq 11$。其余8个数字依次表示颜色A到H的亮度，每个亮度的值为正整数且小于256。

接下来的$n$行每行包含8个字母（A到H之间），表示一个八角形边缘的颜色，按顺时针方向给出。每种颜色可能在八角形中出现零次或多次。不同颜色可能具有相同的亮度，但这并不表示它们是同一种颜色。

输出格式

对于每个数据集，输出一行：如果无法用所有八角形构造手镯，则输出“impossible”；否则输出连接处亮度的最小总和。注意：如果您的解决方案逐个考虑所有可能的排列和旋转，可能会因超时而被判定为无效。