Fastest Route

あなたの所属する知的プログラミングサークル (通称 Intelligent Clever Programming Circle, ICPC)では，今大掃除の最中である． 部室には，歴代の先輩たちの残していったさまざまなアイテムが所狭しと放置されている． あなたが棚を整理していると，奥に大量のレトロゲームが封印されているのを発見した． その中のいくつかに見覚えがあったあなたは，久々にそのゲームを遊んでみることにした．

見つけたゲームの詳細は次の通りである．

このゲームには1番から N 番までの N 個のステージがあり，任意の順に攻略することができる． また，1から N まで番号付けられた装備があり，それらの装備を使用することでステージの攻略時間を短縮することができる． ゲームを始めた段階では装備は一つも持っていないが， i 番のステージを攻略すると i 番の装備を入手することができ，一度入手した後は何度でも使用できる． 装備は一ステージで一種類だけしか使用することができないが，異なるステージで同じ装備を使用することはできる．

あなたは昔このゲームをクリアしたことがあるので，各装備に対して，その装備を使用したときに各ステージを攻略するのにかかる時間をすべて把握している． ただ普通にクリアするだけではつまらないので，あなたは全てのステージを攻略し終わるまでにかかる時間を最小にしようと考えた． そのため，あなたはICPCでの経験を生かして，各情報を与えたときに全てのステージを攻略し終わるまでにかかる時間の最小値を計算するプログラムを書くことにした．

入力は複数のデータセットからなる． 入力の終わりは1つのゼロからなる行によって与えられる． 各データセットは一つのゲームに関する情報を表し，その形式は以下の通りである．

N
t10 t11 ... t1N
t20 t21 ... t2N
...
tN0 tN1 ... tNN

データセットの最初の行は1つの整数 N からなり，ステージの数を表す． 続く N 行は N+1 個の整数からなり，ステージの攻略時間を表す． ti0 は i 番のステージを装備なしで攻略するのにかかる時間である． ti j ( j > 0)は i 番のステージを j 番の装備で攻略するのにかかる時間である．

それぞれの値は次の制約を満たしている．

• 1 ≤ N ≤ 16
• 1 ≤ ti j ≤ 100,000

それぞれのデータセットに対して，全てのステージを攻略し終わるまでにかかる時間の最小値を表す整数を1行に出力せよ．出力行にはこの数値以外の文字を含んではならない．