차량 개조 (Pimp My Ride)

거리에는 대대적인 정비가 필요한 자동차, 오토바이, 트럭을 비롯한 온갖 차량이 넘쳐난다. 당신은 대형 방송국에서 넉넉한 예산을 지원받아 이 차량들을 개조하는 일을 맡았다.

할 일이 워낙 많아, 도색이나 실내 장식 같은 개별 작업은 전문 정비소에 맡기기로 했다. 각 정비소는 특정 종류의 작업만 처리하므로 작업마다 서로 다른 정비소가 필요하다. 게다가 정비소는 차의 상태가 이미 좋을수록 더 많은 비용을 청구하는 경향이 있다. 예를 들어 도색 담당자는 실내가 온통 가죽으로 꾸며진 차에 웃돈을 붙일 수 있다. 이러한 추가 요금은 이미 끝난 작업이 무엇인지에 따라 달라지므로, 당신은 작업 순서를 잘 정해 비용을 아끼려 한다.

작업은 $1$번부터 $n$번까지 번호가 매겨져 있다. 각 작업 $i$에는 기본 요금이 있고, $i \ne j$인 순서쌍 $(i, j)$마다 추가 요금 $s_{ij}$(미국 달러)가 정의된다. 즉, 작업 $j$가 작업 $i$보다 먼저 완료된 경우에 한해 작업 $i$에 대해 $s_{ij}$만큼을 더 지불해야 한다. 어떤 작업 순서의 총비용은 모든 작업에 대해, 각 작업의 기본 요금과 그 작업을 수행하는 시점에 이미 끝나 있는 작업들에 대한 추가 요금을 더한 값이다. 모든 작업을 끝내는 데 드는 최소 총비용을 구하라.

첫 줄에는 시나리오의 개수가 주어진다.

각 시나리오는 작업 수 $n$($1 \le n \le 14$)이 적힌 줄로 시작한다. 이어지는 $n$개의 줄은 비용 행렬을 나타내며, 각 줄에는 정확히 $n$개의 정수가 있다. $i$번째 줄($1 \le i \le n$)에서 $i$번째 정수는 작업 $i$의 기본 요금이고, $j$번째 정수($j \ne i$)는 작업 $j$가 먼저 완료되었을 때 작업 $i$에 적용되는 추가 요금이다. 모든 요금과 추가 요금은 $100000$ 이하의 음이 아닌 정수이다.

각 시나리오에 대해 먼저 다음 줄을 출력한다.

Scenario #i:

여기서 $i$는 $1$부터 시작하는 시나리오 번호이다. 그다음 줄을 출력한다.

You have officially been pimped for only $p

여기서 $p$는 최소 총비용이다. 서로 이웃한 시나리오 사이에는 빈 줄을 하나 출력한다.