Description

Farmer John’s farm is short of water.

He decides to bring water to his $n$ fields. He can dig some wells and build channels between fields to connect them for water supply. Digging a well in field $i$ costs $W_i$ units. Connecting field $i$ and field $j$ costs $P_{i,j}$ (with $P_{j,i} = P_{i,j}$) units.

Find the minimum amount of money FJ needs so that every field is either connected to a field that has water or has its own well.

Input Format

The first line contains an integer $n$.

The next $n$ lines each contain an integer $W_i$.

The next $n$ lines each contain $n$ integers; the $j$-th number in the $i$-th line is the cost $P_{i,j}$ to connect field $i$ and field $j$.

Output Format

Output the minimum cost.

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

9

Hint

Constraints: For $100\%$ of the testdata, $1 \leq n \leq 300$, $1 \leq W_i \leq 10^5$, $0 \leq P_{i,j} \leq 10^5$.

Translated by ChatGPT 5