006 - 伝説の肉体

問題

Mr.Four 「倒れるだけで腹筋ワンダーコアー」

Mr.Fourは最近自分が太っていることを気にしています。 しかし、ダイエットは過酷ときいていたMr.Fourは痩せるのを半ばあきらめていました。 しかし、Mr.Fourは次のような噂を耳にしました。1番からN番までの"ワンダーコア"があり、 このN個の"ワンダーコア"をすべて手に入れることによって伝説の肉体を手に入れられるという 噂をききました。Mr.Fourは伝説の肉体を手に入れるため、"ワンダーコア"を集めることにしました。 各"ワンダーコア"は世界のワンダーコアlerたちが所持しています。"ワンダーコア"を手に入れるには 彼らに誠意を示さねばなりません。つまり彼らの前で何度か"わんだーこあ"しなければならないのです。 しかし、Mr.Fourはなるべく疲れることなくすべての"ワンダーコア"を手に入れたいと思っています。 つまり、より少ない"わんだーこあ"でN個の"ワンダーコア"すべてを集めたいです。 Mr.Fourの弟子である君たちがN個の"ワンダーコア"すべて集めるときの最小の"わんだーこあ"の回数を 求めてあげてほしい。
[注意！注意！注意！]
"ワンダーコア"はものの名前であり、"わんだーこあ"はワンダーコアを使って腹筋することである。

詳細は次の通りである。
1番からN番までの"ワンダーコア"があり、任意の順で"ワンダーコア"を集めることができます。そして、 集めた"ワンダーコア"を使うことでワンダーコアlerの前で行う"わんだーこあ"の回数を短縮することができます。たとえば、"ワンダーコア"をひとつももっていない場合、10回"わんだーこあ"をする必要があるのに対し、1番目の"ワンダーコア"を使うことにより、5回に短縮できるというような感じです。集め始めた段階では"ワンダーコア"はひとつも持っていないものとする。一度入手した"ワンダーコア"は その後何度でも使用できる。"ワンダーコア"は一度に1種類だけしか使用できないが、異なる人の前で "わんだーこあ"する時に同じ"ワンダーコア"を使用することができる。

あなたは"ワンダーコア"についてよく調べていたため、各"ワンダーコア"使ってワンダーコアlerの前で行う 必要のある"わんだーこあ"の回数をすべて把握している。すべての"ワンダーコア"を集め終わるために 必要な"わんだーこあ"の回数の最小値を計算するプログラムを作成してください。

入力

N
c1,0 c1,1 ・・・ c1,N
c2,0 c2,1 ・・・ c2,N
 :
cN,0 cN,1 ・・・ cN,N

1行目に1つの整数Nが与えられる。
N : "ワンダーコア"の数 (1 ≦ N ≦ 16)
2行目からN+1行目にN個の整数c_i,jが半角空白区切りで与えられる。
c_i,0 : i番目の"ワンダーコア"を"ワンダーコア"なしで手に入れるときの必要な"わんだーこあ"の回数 (1 ≦ c_i,0 ≦ 100000)
------------------------7月23日木曜日午後2時07分 追記 --------------------------------
"ワンダーコア"なしで手に入れる場合が最小の必要な"わんだーこあ"の回数の場合もある。 ---------------------------------------------------------------------------------
c_i,j (j > 0) : i番目の"ワンダーコア"を手に入れるためにj番目の"ワンダーコア"を使用したときの必要な"わんだーこあ"の回数 (1 ≦ c_i,j ≦ 100000)

出力

すべての"ワンダーコア"を手に入れるために必要な"わんだーこあ"の回数の最小値を求めて、1行に整数で出力せよ。

入出力例

入力例1

2
10 2 5
10 2 5
3
100 25 30 20
100 45 60 30
100 50 20 50
5
50 20 32 44 47 28
45 30 16 22 41 32
55 26 34 30 10 48
47 45 27 31 29 37
52 37 36 35 34 33
0

出力例1

12
140
141