No.70 アルゴリズムのお勉強

時間制限:$2.0sec$ / メモリ制限:$256MB$ / tester:ei1333

問題文

大手前プロコンの参加者である君は$N$個のアルゴリズムを勉強しようとしている。

それぞれのアルゴリズムは、$t_i$時間勉強すると理解できる。

また、任意の二つのアルゴリズムの組み合わせについて、$i$を理解してから$j$を勉強すると勉強にかかる時間が$a_{ij}$時間短くなるという依存関係がある。

君はどのような順番で勉強してもよいが、できるだけ短い時間で$N$個すべてのアルゴリズムを理解したい。

最短で$N$個のアルゴリズムを理解するには何時間かかるだろうか？

制約

  • $1≦N≦16$
  • $1≦t_i≦1000$
  • $0≦a_{ij}≦50$
  • $a_{ii} = 0$
  • 勉強にかかる時間が$0$以下になる事はない。

入力形式

入力は以下の形式で標準入力から与えられる。 


N
t1 t2 … tN
a_11 a_12 … a_1N
a_21 a_22 … a_2N
…
a_N1 a_N2 … a_NN

出力

全てのアルゴリズムを理解するのにかかる最短時間を出力してください。

入出力例

入力1 

3
5 6 7
0 1 2
1 0 1
2 2 0
出力1 

13

例えば、3->1->2の順番で勉強する事で達成できます。