밝은 팔찌

팔찌 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 하나만 주어진다.

각 데이터 집합은 공백으로 구분된 아홉 개의 정수가 있는 줄로 시작한다. 첫 번째 정수는 팔찌를 이루는 팔각형의 개수 $n$이며 $4 \le n \le 11$이다. 나머지 여덟 개의 정수는 색 A부터 H까지의 밝기를 순서대로 나타낸다. 각 밝기는 양수이고 $256$보다 작다.

이어지는 $n$개의 줄에는 각각 A부터 H까지의 문자 여덟 개가 주어지며, 한 팔각형의 변 색을 시계 방향 순서로 나타낸다. 같은 색이 한 팔각형에 여러 번 나타날 수 있다. 서로 다른 색이 같은 밝기를 가질 수 있으나, 그렇다고 같은 색이 되는 것은 아니다.

각 데이터 집합마다 한 줄을 출력한다. 모든 팔각형을 사용해 팔찌를 만들 수 없으면 impossible을 출력한다. 그렇지 않으면 이음매 밝기의 최소 합을 출력한다.

주의: 가능한 모든 순서와 회전을 하나하나 시도하면 시간 안에 끝나지 않는다.