Famer John希望把水源引入他的 $N$ 个牧场，牧场的编号分别是 $1 \sim N$。他将水源引入某个牧场的方法有两个，一个是在牧场中打一口井，另一个是将这个牧场与另一个已经有水源的牧场用一根管道相连。在牧场 $i$ 中打井的费用是 $W_i$。把牧场 $i$ 和 $j$ 用一根管道相连的费用是 $P_{i,j}$。请你求出Farmer John最少要花多少钱才能够让他的所有牧场都有水源。

第 $1$ 行: 一个正整数 $N$. 第 $2 \sim N+1$ 行: 第 $i+1$ 行包含一个正整数 $W_i$. 第 $N+2 \sim 2N+1$ 行: 第 $N+1+i$ 行包含 $N$ 个用空格分隔的正整数，第 $j$ 个数表示 $P_{i,j}$。 - $1 \le N \le 300$ - $1 \le W_i \le 100000$ - $1 \le P_{i,j} \le 100000 \ (i \ne j)$ - $P_{i, j} = P_{j, i}$ - $P_{i, i} = 0$

最少要花多少钱才能够让所有牧场都有水源。

总共有四个牧场。在 $1$ 号牧场打一口井需要 $5$ 的费用,在 $2$ 号或者 $3$ 号牧场打井需要 $4$ 的费用，在 $4$ 号牧场打井需要 $3$ 的费用。在不同的牧场间建立管道需要 $2, 3$ 或 $4$ 的费用。Farmer John需要在 $4$ 号牧场打一口井，然后把所有牧场都用管道连到 $1$ 号牧场上，总共的花费是 $3+2+2+2=9$。