연습 시즌

프로야구팀 X와 Y가 정해진 순서로 7개 도시를 방문하며 연습 시즌을 보낸다. 7개 도시는 c1, c2, c3, c4, c5, c6, c7로 나타낸다. 두 팀은 연습 시즌을 시작하는 날과 끝내는 날이 반드시 같아야 한다.

연습 시즌 동안 각 팀은 하루에 도시 하나를 방문해 훈련하거나, 호텔을 잡아 하루를 통째로 쉰다(휴식일). 각 팀이 방문할 도시의 순서는 이미 정해져 있어 바꿀 수 없지만, 그 사이사이에 휴식일을 상황에 맞게 자유롭게 끼워 넣을 수 있다.

예를 들어 한 팀이 방문할 도시 순서가 S = <c1, c2, c3, c1, c4, c1, c5, c4>라면, 중간에 휴식일 R을 넣어 아래와 같은 새로운 일정을 만들 수 있다.

• S1 = <c1, c2, R, c3, c1, R, R, c4, c1, c5, R, c4>
• S2 = <R, R, c1, c2, c3, c1, R, c4, R, c1, c5, c4>

야구장 사용료. 한 팀이 야구장에서 훈련하는 비용은 7개 도시 모두 똑같이 $C$이다. 두 팀 X와 Y가 같은 날 같은 야구장을 함께 쓰면 전체 비용이 $C$이므로 각 팀은 $C/2$씩만 내면 되어 이득이다. 서로 다른 야구장에서 따로 훈련하면 각각 $C$씩, 전체 $2C$가 든다.

호텔 비용. 휴식일에는 호텔 하나를 통째로 빌린다. 호텔을 빌리면 독점 사용료 $D$가 한 번 들고, 머무는 기간에 따라 하루당 $d$가 추가로 든다. 즉 한 팀이 어떤 호텔에 연속으로 $w$일 머물면 $D + w \cdot d$를 낸다. 예를 들어 $D = 4$, $d = 1$일 때 연속 5일을 머물면 $4 + 1 \cdot 5 = 9$를 내지만, 5일을 서로 떨어진 날에 하루씩 나누어 머물면 독점료를 다섯 번 내고 사용료도 5일치를 내므로 $5 \cdot 4 + 5 \cdot 1 = 25$가 든다.

두 팀의 방문 순서를 그대로 두고 별다른 조정 없이 일정을 짜면 아래 표-1과 같다. 이때 Y팀은 시작과 끝을 X팀과 맞추기 위해 마지막 이틀(7일째, 8일째)을 휴식일로 쓴다.

표-1. 간단한 일정 A

야구장 사용료 $C = 3$, 호텔 독점료 $D = 4$, 하루 사용료 $d = 1$일 때, 표-1의 일정대로 하면 두 팀이 내야 하는 비용은 아래 표-2와 같다.

표-2. 일정 A의 비용

따라서 전체 비용은 $6 \cdot 6 + 8 + 4 = 48$이다. 이제 조금 다른 일정을 생각해 보자. 아래 표-3처럼 Y팀 일정에 휴식일을 적절히 넣으면 두 팀이 야구장을 함께 쓰는 날이 늘어 전체 비용을 줄일 수 있다.

표-3. 일정 B

이 경우 전체 비용은 $3 \cdot 6 + 8 \cdot 2 = 34$로, 일정 A보다 $48 - 34 = 14$만큼 아낄 수 있다. 다만 최적의 일정은 $C$, $D$, $d$ 값에 따라 달라질 수 있음에 유의하자.

X와 Y 두 팀의 방문 도시 순서가 주어질 때, 두 팀이 내야 하는 비용의 합이 최소가 되는 가장 좋은 일정을 찾아 그 최소 전체 비용을 출력하여라.

입력은 표준 입력으로 주어진다. 첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스는 세 줄로 이루어진다.

• 첫 줄에는 정수 $C$, $D$, $d$가 공백 하나로 구분되어 차례로 주어진다. 세 값은 모두 10 이하의 양의 정수이다.
• 이어지는 두 줄에는 각각 X팀과 Y팀이 방문할 도시의 순서가 공백 하나로 구분되어 주어지며, 줄의 끝은 숫자 0으로 표시된다. 각 도시는 1부터 7까지의 정수이다.

방문할 도시의 개수 $N$은 $2 < N < 100$을 만족한다.

각 테스트 케이스마다 연습 시즌을 마치는 데 드는 최소 비용(X와 Y 비용의 합)을 한 줄에 하나씩 출력한다.