휴학의 길은 멀구나

문제 정보

문제

이미 알고있는 사실이겠지만, KAIST에서 휴학을 하기 위해선 많은 절차가 필요하다. 지도교수님도 찾아뵈어야 하고, 도서관도 가야하고.. 갈 곳이 많은 게 현실이다. 당신은 휴학계를 어떻게든! 제출하기 위해 방문해야 하는 점들을 적어도 한번 씩 방문하고 돌아오는 시간을 최소화하고 싶다.

휴학을 하기 위해선 총 $N$군데를 방문해야 하는데 각각 번호가 $1,2, \cdots ,N$으로 나타난다. 당신은 $1$번점인 학적팀에서 출발하여 $2, \cdots ,N$점을 적어도 한번 씩 방문하고 다시 1번점인 학적팀으로 돌아오려고 한다. 각 점 사이의 거리는 인접행렬로 주어지며 각 거리는 언제나 최단거리이다.

거리는 주어지지만 속도는 교통수단에 따라 다르다. KAIST에서 이용할 수 있는 교통수단은 총 3가지이다.
* OLEV(셔틀버스) : $N$개의 점 $B_{1},B_{2}, \cdots ,B_{N}$ 를 순서대로 이동한다. $B_{1},B_{2}, \cdots ,B_{N}$은 $1$부터 $N$까지의 수중 하나이고 모두 다르며, OLEV는 $B_{N}$를 방문한 뒤 $B_{1}$으로 이동한다. OLEV는 $B_{1}$에서 시간이 0일 때 출발하여, 다음 점을 이동할 때까지 그 거리만큼 시간이 소요된다. 즉, OLEV는 어느 점에서 타이밍을 맞춰야 이용할 수 있는 교통수단이다.
* 타슈(자전거) : 타슈는 KAIST 내에서 단기간 빌려쓸 수 있는 자전거이며 $N$개의 점에 설치되어있다. 단, 타슈는 한번 이용하는데 요금이 들기 때문에, 제한된 예산을 가지고 있는 당신은 이를 $M$번 이하 이용 가능하다. 이 때 걸리는 시간은 거리의 2배이다. 단, 건물을 방문하기 전에는 타슈를 반납해야 한다.
* 걷기 : 가장 느린 방법이며, 거리의 4배 만큼 시간이 소요된다.

LEV를 타거나 내리는 것, 타슈를 빌리거나 반납하는 것, 건물을 방문하는 것은 시간이 소요되지 않는다고 가정하자. 현재 당신은 시간 $T$에 학적팀에 있다. 모든 점을 적어도 한번 방문하고 빨리 학적팀으로 돌아오려고 할 때, 그 시각을 구하자. 휴학을 위해서!

입력

입력은 여러 개의 테스트 케이스로 구성된다. 입력의 첫 줄에는 테스트케이스의 개수가 주어진다.
각 테스트 케이스에 대해, 첫 번째 줄에는 정수 $N$이 주어진다.$(2 \le N \le 15)$
다음 $N$개의 줄에는 거리에 대한 정보들이 주어지는데 각 줄마다 $N$개의 음이 아닌 정수가 주어진다. $i$번째 줄의 $j$번째 숫자 $(1 \le i,j \le N)$의 의미는 $i$번 점에서 $j$번 점까지의 최단거리이다. ($i=j$인 경우를 제외하고는 양의 정수$( \le 100)$가 주어지며 $(i,j)$의 값과 $(j,i)$의 값은 같다)
그 다음 줄엔 $B_{1},B_{2}, \cdots ,B_{N}$을 나타내는 $N$개의 정수가 차례대로 주어진다.
마지막 줄엔 현재 시간을 나타내는 정수 $T$와 타슈 이용제한 수인 $M$이 주어진다. $(0 \le T \le 10,000 , 0 \le M \le N)$

출력

각 테스트 케이스마다 최대한 빨리 모든 점을 적어도 한 번씩 방문하고 학적팀으로 돌아왔을 때의 시간을 출력한다.

예제 입력

2
3
0 2 1
2 0 3
1 3 0
2 3 1
0 1
4
0 2 2 3
2 0 3 2
2 3 0 1
3 2 1 0
4 2 3 1
2 2

예제 출력

10
16

노트

예제 설명(첫번째 예제)

1번 점인 학적팀에서 타슈를 타고 2번 점으로 이동한다. (시간 4 소요)
다음 시간 6 때 OLEV를 타고 시간 9 때 3번 점에 도착한다.
3번 점에서 다시 OLEV를 타고 시간 10 때 1번 점에 도착한다.

0개의 댓글이 있습니다.