問題文

この国には $N$ 個の都市があり、すべての都市は互いに道路で結ばれています。都市 $i$ と $j$ の間を移動するのにかかる時間は、$D_{ij}$ です。

また、チェーン店のカフェ「Math Cafe」の店舗が、この国のすべての都市にちょうど $1$ つずつあります。時刻 $t = 0$ において、カフェ「Math Cafe」の店舗すべてにおいて、火事が同時に発生しました。

あなたは消防士です。時刻 $t = 0$において都市 $1$ にいて、すぐに都市 $1$ のカフェ「Math Cafe」の店舗の火事を鎮火しました。

ここで、都市 $i$ のカフェ「Math Cafe」の各店舗が鎮火された時刻がそれぞれ $t_i$ であったとき、悲しみ $S$ は次の式で定義されます。 \[S = \sum_{1\le i\le N} t_i \]

達成可能な悲しみ $S$ の最小値を求めてください。ただし、鎮火にかかる時間は無視できるものとします。

制約

• $2 \leq N \leq 16$
• $1 \leq D_{ij} \leq 10000$ $(1 \leq i , j \leq N$ かつ $i \neq j)$
• $D_{ii} = 0$ $(1 \leq i \leq N)$
• $D_{ij} = D_{ji}$ $(1 \leq i , j \leq N)$
• $1 \leq i , j \leq N$ について、任意の $k$ $(1 \leq k \leq N)$ に対して $D_{ij} \leq D_{ik} + D_{kj}$
• 入力はすべて整数

入力

$N$
$D_{11}$ $D_{12}$ $\dots$ $D_{1N}$
$D_{21}$ $D_{22}$ $\dots$ $D_{2N}$
$D_{31}$ $D_{32}$ $\dots$ $D_{3N}$
$\vdots$ 
$D_{N1}$ $D_{N2}$ $\dots$ $D_{NN}$

出力

最後に改行してください。

サンプル

2
0 1942
1942 0

1942

4
0 3 6 11           
3 0 4 9
6 4 0 5
11 9 5 0

22