C. Sprinkler Piping
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are replacing the sprinkler system in your front yard and need to connect a set of sprinkler heads with pipes.

Water enters the sprinkler system from a faucet at a fixed location in space. A pipe needs to carry this water to one sprinkler head, and from there to a second sprinkler head, and so on. The pipe cannot branch: it must visit every sprinkler head exactly once, but can connect the sprinkler heads in any order.

Given the cost of laying pipe between the faucet and every sprinkler head, and between every head and every other head, compute the cheapest cost you must pay to connect water to every sprinkler head using a single non-branching pipe.

Input

The first line of input contains an integer $$$N$$$ $$$(1 \leq N \leq 15)$$$, the number of sprinkler heads in your front yard.

The next line of input contains $$$N$$$ space-separated integers $$$f_i$$$ $$$(0 \leq f_i \leq 10^6)$$$, the cost of connecting the faucet to sprinkler head $$$i$$$.

Each of the next $$$N$$$ lines of input contain $$$N$$$ space-separated integers each. The $$$j$$$th integer on the $$$i$$$th row, $$$c_{ij}$$$ $$$(0 \leq c_{ij} \leq 10^6)$$$, is the cost of connecting sprinkler head $$$i$$$ to sprinkler head $$$j$$$ with pipe. It is guaranteed that $$$c_{ij} = c_{ji}$$$ and that $$$c_{ii} = 0$$$ for every $$$i, j$$$ (though it is invalid to connect a sprinkler head to itself in any case.)

Output

Print the cheapest total cost of connecting the faucet to all sprinkler heads using a single, non-branching pipe.

Examples
Input
4
7 8 1 2
0 3 1 4
3 0 8 8
1 8 0 5
4 8 5 0
Output
11
Input
1
1000000
0
Output
1000000
Input
5
1000 1000 1 1000 1000
0 1 1000 1000 1000
1 0 1000 1000 1
1000 1000 0 1 1000
1000 1000 1 0 1
1000 1 1000 1 0
Output
5
Note

In the first sample, there are $$$4$$$ sprinkler heads. The costs of connecting the faucet to each sprinkler head are $$$$$$f = \begin{bmatrix}7 & 8 & 1 & 2\end{bmatrix}.$$$$$$

One optimal way to connect the sprinkler heads is to use the order $$$$$$\text{faucet} \rightarrow 4 \rightarrow 3 \rightarrow 1 \rightarrow 2.$$$$$$

The total cost of this order is $$$$$$f_4 + c_{4,3} + c_{3,1} + c_{1,2}.$$$$$$

Substituting the values from the input, this is $$$$$$2 + 5 + 1 + 3 = 11.$$$$$$

Therefore, the cheapest total cost is $$$11$$$.