시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 91 56 48 65.753%

문제

두 프로야구팀 X 와 Y 가 7 군데의 도시를 정해진 순서로 방문하면서 연습 시즌을 보낸다. 7 개의 도시는 {c1, c2, c3, c4, c5, c6, c7}로 표시되어 있다. 두 팀 X 와 Y 가 연습 시즌을 시작하는 날과 마치는 날은 반드시 동일해야 한다. 이 연습 시즌 동안 각 팀은 도시를 방문해서 연습 훈련을 하거나 또는 한 호텔을 정해서 하루 종일 휴식(휴식일)을 가진다. 각 팀이 방문해야 하는 도시들의 순서는 이미 각각 정해져 있지만 그 중간에 쉬는 휴식일은 따로 정해져 있지 않다. 따라서 방문해야 할 도시들의 순서는 바꿀 수 없지만 그 중간에 휴식일은 상황을 봐가면서 적절히 선택할 수 있다. 

예를 들어 연습시즌 동안 한 팀이 방문해야 할 도시의 순서가 S=<c1, c2, c3, c1, c4, c1, c5, c4> 와 같다면 각 팀은 그 중간에 휴식일을 넣을 수 있다. 예를 들어 아래 두 개의 일정은 S 에 중간 중간 휴식일이 들어간 상태의 새로운 일정의 예 S1 과 S2 를 보여주고 있다. 

  • 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 이지만 같은 야구장을 쓰면 각각 C/2 만 내면 되기 때문에 전체 비용은 C 가 된다. 그런데 각 팀이 호텔에서 휴식일로 쉴 때의 경비계산은 좀 다르다. 

연습 시즌 동안 각 팀은 원기회복을 위하여 중간에 휴식일을 가질 수 있다. 이 경우에는 한 호텔을 모두 빌어서 전체가 쉰다. 그런데 호텔에서는 야구팀이 호텔 전체를 빌려서 사용하기 때문에 일단 호텔 전체를 빌릴 경우 독점사용비로 D 만큼 요구한다. 그리고 사용하는 기간에 따라서 추가로 하루당 d 만큼의 비용을 요구한다. 즉 야구팀이 어떤 호텔에 w 일간 연속해서 머물 경우 D+w*d 만큼 지불해야 한다. 예를 들어 전체간 D=4, d=1 인 경우에 한 팀이 5 일간 연속해서 호텔에 머물 경우 전체 비용은 4 + 1*5 = 9 만큼의 비용을 내야 한다. 만일 5 일을 각각 따로 따로 떨어진 날로 하루씩 머물 경우에는 모두 5 번의 독점료를 내야 하고 또한 5 일 동안의 사용료를 내야 하므로 전체 비용은 5*4+5*1=25 가 된다. 

두 팀의 도시 방문순서가 주어졌을 때 특별한 변화 없이 각각 그대로 방문하는 연습시즌 일정을 짜면 아래 표-1 과 같아진다. 이 경우 Y 팀은 앞의 가정대로 연습시즌의 처음과 끝을 X 팀과 맞추기 위해서 마지막 이틀, 7 일과 8 일째 날은 휴식일로 사용하고 있다. 

  Day1 Day2 Day3 Day4 Day5 Day6 Day7 Day8
X c1 c3 c4 c5 c2 c6 c6 c1
Y c3 c4 c2 c6 c6 c1 R R

표-1. 간단한 일정-A

만일 야구장 사용료가 C=3 이고, 호텔독점료 D=4, 일일 사용료 d=1 일 때 , 위 표-1 에 있는 일정대로 하면 X 와 Y 가 지불해야 하는 전체 비용은 아래 표-2 와 같다. 

Day Day1 Day2 Day3 Day4 Day5 Day6 Day7 Day8
X c1 c3 c4 c5 c2 c6 c6 c1
Y c3 c4 c2 c6 c6 c1 R R
X 비용 3 3 3 3 3 3 3 3
Y 비용 3 3 3 3 3 3 5 1
6 6 6 6 6 6 8 4

표 2. 일정-A 에 따라서 연습시즌을 지낼 경우 비용.

따라서 X 와 Y 가 지불해야 하는 전체 비용은 6*6 + 8 + 4 = 48 이다. 일정-A 와 조금 다른 다른 일정을 잡아보자. 만일 아래 표-3 과 같이 Y 팀의 일정에 휴식일을 적절히 넣어서 조정하면 두 팀이 야구장을 공동으로 쓰는 날이 늘어나므로 전체 비용을 줄일 수 있다. 

Day Day1 Day2 Day3 Day4 Day5 Day6 Day7 Day8
X c1 c3 c4 c5 c2 c6 c6 c1
Y R c3 c4 R c2 c6 c6 c1
X 비용 3 1.5 1.5 3 1.5 1.5 1.5 1.5
Y 비용 5 1.5 1.5 5 1.5 1.5 1.5 1.5
8 3 3 8 3 3 3 3

표 3. 일정-B

따라서 전체 비용은 3*6 + 8*2 = 34 이 되어 일정-A 에 따른 비용에 비해서 48-34 = 14 만큼 절약할 수 있다. 그러나 최적의 일정은 C, D 그리고 d 값에 따라서 다르게 결정될 수 있음을 유의해야 한다. 

여러분은 X 와 Y 팀의 방문도시 일정이 주어졌을 때 두 팀이 지출해야 하는 비용의 합을 최소로 가는 가장 좋은 일정을 구하고 그 전체 비용을 출력하는 것이다. 아래 입출력의 예를 잘 살펴보면 이 문제를 잘 이해할 수 있을 것이다. 

입력

입력은 표준 입력으로 들어온다. 입력은 모두 T 개의 테스트 케이스가 있다. 테스트 케이스의 전체 개수는 첫 줄에 주어진다. 각 테스트 케이스는 3 개의 줄로 이루어져 있다. 첫 라인에는 C, D, d 를 나타내는 정수 값이 차례대로 하나의 공백을 두고 나타난다. 각 숫자는 모두 10 이하의 양의 정수이다. 그 다음 이어지는 두 개의 줄에는 방문해야 할 도시의 순서가 하나의 공백을 두고 나타난다. 각 도시는 1 부터 7 까지의 정수로 표시된다. 그리고 그 끝은 숫자 0 으로 표시되어 있다. 방문해야 할 도시의 개수 N 은 2 < N < 100 로 제한되어 있다. 

출력

여러분의 프로그램은 표준출력에 써야 한다. 각 테스트 케이스에 해당되는 정답, 즉 연습시즌을 마칠 수 있는 최소의 비용(X 와 Y 비용의 합)을 출력해야 한다. 

예제 입력

5
4 5 2
3 5 6 7 5 0
3 5 6 7 0
10 5 1
1 2 3 4 5 6 7 0
2 3 4 5 6 7 1 0
2 9 1
1 2 3 4 5 6 7 0
2 3 4 5 6 7 1 0
8 1 3
1 2 3 4 5 6 7 6 5 4 3 0
2 5 4 0
4 3 3
5 6 7 1 4 5 6 7 0
3 5 6 7 0

예제 출력

27
92
28
115
51

힌트