Description

Developing the mining industry naturally requires mines first. Little FF spent one-thousandth of the wealth obtained from the last expedition to have $n$ mines dug on the island. However, he seems to have forgotten to consider the power supply issue for the mines...

To ensure the power supply, Little FF came up with two solutions:

1. Build a power station on this mine at a cost of $v$ (the output power of the power station can supply any number of mines).
2. Establish a power grid between this mine and another mine that already has a power supply, at a cost of $p$.

Little FF hopes that you, the chief engineer of the "NewBe_One" project, can help him devise a plan to ensure power supply for all mines at the minimum cost.

Input Format

The first line contains an integer $n$, representing the total number of mines.

Lines $2\sim n+1$ each contain an integer, where the $i$-th number $v_i$ represents the cost of building a power station on the $i$-th mine.

This is followed by an $n\times n$ matrix $p$, where $p_{i,j}$ represents the cost of establishing a power grid between the $i$-th mine and the $j$-th mine (the data ensures $p_{i,j}=p_{j,i}$ and $p_{i,i}=0$).

Output Format

Output only one integer, representing the minimum cost to ensure all mines receive sufficient power.

Sample 1

Little FF can choose to build a power station on mine $4$ and then establish power grids between all mines and it, with a total cost of $3+2+2+2=9$.

4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0

9

Data Range and Hints

For $30\%$ of the data: $1\le n\le50$;
For $100\%$ of the data: $1\le n\le 300,0\le v_i, p_{i,j}\le 10^5$.