English text is not available in this practice contest.

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

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

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

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

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

N
t₁₀ t₁₁ ... t_1N
t₂₀ t₂₁ ... t_2N
...
t_N0 t_N1 ... t_NN

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

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

• 1 ≤ N ≤ 16
• 1 ≤ t_{i j} ≤ 100,000

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

3
100 100 100 100
100 1 100 100
100 1 1 100
3
100 100 1 100
200 102 100 102
100 100 1 100
7
100 100 60 60 70 70 70 90
100 50 100 55 45 45 55 44
100 50 60 100 51 50 55 30
100 70 10 20 1 10 10 40
200 90 10 30 10 10 10 30
150 200 12 1 11 11 1 30
10000 1200 1100 1100 1200 1200 1090 1
0

102
202
1301