注意

Python使いの方はPyPyで提出することをお勧めします。
(Python素人のwriterが書いたコードでは最悪ケースで Python 4630ms, PyPy 240ms)

問題文

あなたは冷酷無比なベテラン刑事です。
集団詐欺グループのアジトをついに突き止めたあなたは、アジトへの突入作戦を実行し、
見事詐欺グループの全メンバー$N$人を捕まえることに成功しました。

捕らえられたメンバーは1人1部屋ずつ、合計$N$部屋の取調室に収容されています。あなたの目標は、
全メンバーを自白させることです。

事前に行われた捜査から、詐欺グループの各メンバーはそれぞれ頼りにしているメンバーが何人か(0人以上)いる
ことがわかっています。頼りにしているメンバーが全員自白したと知った(もしくは最初から誰も頼りにしていなかった)
とき、そのメンバーは心の拠り所を失い、自分の犯した過ちを全て自白することでしょう。

前述の通り、各メンバーは1人ずつ別々の取調室に入れられています。つまり、他のメンバーが自白したかどうか
はあなたを通してしか知ることが出来ません。これは何を意味するでしょうか？

あなたはメンバーに対して嘘をつくことが出来ます。具体的には、メンバー$i$がまだ自白していないにも関わらず、
$i$以外のメンバー$j$に「$i$は自分のやったことを洗いざらい話して楽になったぞ、お前も楽になったらどうだ」
とハッタリをかけることが出来ます。いくら冷酷無比なあなたでも、$i$が自白したという嘘をつくことには$i$に対して
若干の申し訳なさを感じてしまいます。しかし、慣れというのは恐ろしいもので、一度$i$が自白したという嘘をついて
しまえば、あとは何回同じ嘘をついても申し訳なさを全く感じません(冷酷無比なので)。

詐欺グループの各メンバーが頼りにしているメンバーのリスト$X$、及びあなたが「メンバー$i$が自白した」という
嘘を初めてついたときに感じてしまう申し訳なさ$A_i$が与えられます。全メンバーを自白させるために感じざる
を得ない申し訳なさの総和の最小値を求めてください。

「メンバーが自白した」という*事実*を伝える行為に対しては申し訳なさを感じないことに注意してください
(わからなければサンプルの説明を見てください)。

入力

$N$
$X_{11}$ $X_{12}$ $\cdots$ $X_{1N}$
$X_{21}$ $X_{22}$ $\cdots$ $X_{2N}$
$\vdots$
$X_{N1}$ $X_{N2}$ $\cdots$ $X_{NN}$
$A_1$ $A_2$ $\cdots$ $A_N$

入力は全て整数で与えられる。

• $1 \le N \le 18$
• $X_{ij} = 0, 1$ (1ならばメンバー$i$はメンバー$j$を頼りにしている、0ならば頼りにしていない)
• $X_{ii} = 0$ $(1 \le i \le N)$
• $0 \le A_i \le 10^5$

出力

全メンバーを自白させるために感じざるを得ない申し訳なさの総和の最小値を出力してください。最後に改行してください。

サンプル

3
0 1 1
1 0 0
1 0 0
5 3 3

5

3
0 1 1
1 0 0
1 0 0
10 1 1

2

3
0 1 1
1 0 1
1 1 0
1 2 4

3

4
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
10 10 10 10

0