가장 빠른 경로
면접 대비시간 제한8초메모리 제한512 MB
N개의 스테이지와 N개의 장비가 있고, 스테이지 i를 클리어하면 장비 i를 얻으며 각 스테이지는 장비를 최대 하나만 써서 임의 순서로 클리어할 수 있을 때, 모든 스테이지를 클리어하는 최소 총 시간을 구한다.
문제
당신이 속한 지적 프로그래밍 동아리 (통칭 Intelligent Clever Programming Circle, ICPC)는 지금 대청소 중이다. 동아리방에는 역대 선배들이 남긴 온갖 아이템이 가득 쌓여 있다. 선반을 정리하던 당신은 안쪽에 대량의 레트로 게임이 봉인되어 있는 것을 발견했다. 그중 몇 개는 본 기억이 있었기에, 당신은 오랜만에 그 게임을 해 보기로 했다.
발견한 게임의 상세는 다음과 같다.
이 게임에는 1번부터 N번까지 N개의 스테이지가 있고, 임의의 순서로 공략할 수 있다. 또한 1부터 N까지 번호가 붙은 장비가 있고, 그 장비를 사용하면 스테이지 공략 시간을 단축할 수 있다. 게임을 시작한 시점에서는 장비를 하나도 가지고 있지 않지만, i번 스테이지를 공략하면 i번 장비를 입수할 수 있고, 한 번 입수한 뒤에는 몇 번이든 사용할 수 있다. 장비는 한 스테이지에서 한 종류만 사용할 수 있지만, 서로 다른 스테이지에서 같은 장비를 사용할 수는 있다.
당신은 예전에 이 게임을 클리어한 적이 있으므로, 각 장비에 대해 그 장비를 사용했을 때 각 스테이지를 공략하는 데 걸리는 시간을 모두 파악하고 있다. 그냥 평범하게 클리어하는 것만으로는 재미가 없기에, 당신은 모든 스테이지를 공략할 때까지 걸리는 시간을 최소로 하려고 생각했다. 그래서 ICPC에서의 경험을 살려, 각 정보가 주어졌을 때 모든 스테이지를 공략할 때까지 걸리는 시간의 최솟값을 계산하는 프로그램을 작성하기로 했다.
입력
입력은 여러 데이터 세트로 이루어진다. 입력의 끝은 하나의 0으로 이루어진 줄로 주어진다. 각 데이터 세트는 하나의 게임에 관한 정보를 나타내며, 그 형식은 다음과 같다.
N
t10 t11 ... t1N
t20 t21 ... t2N
...
tN0 tN1 ... tNN
데이터 세트의 첫 줄은 하나의 정수 N으로 이루어지며, 스테이지의 수를 나타낸다. 이어지는 N줄은 N+1개의 정수로 이루어지며, 스테이지의 공략 시간을 나타낸다. ti0은 i번 스테이지를 장비 없이 공략하는 데 걸리는 시간이다. ti j (j > 0)는 i번 스테이지를 j번 장비로 공략하는 데 걸리는 시간이다.
각 값은 다음 제약을 만족한다.
- 1 ≤ N ≤ 16
- 1 ≤ ti j ≤ 100,000
출력
각 데이터 세트에 대해, 모든 스테이지를 공략할 때까지 걸리는 시간의 최솟값을 나타내는 정수를 한 줄에 출력하라. 출력 줄에는 이 수치 외의 문자를 포함해서는 안 된다.