휴학의 길은 멀구나

문제 정보

문제

이미 알고있는 사실이겠지만, 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개의 댓글이 있습니다.