题目描述

Farmer John希望把水源引入他的$N$ ($1 <= N <= 300$) 个牧场,牧场的编号是$1~N$.他将水源引入某个牧场的方法有两个,一个是在牧场中打一口井,另一个是将这个牧场与另一个已经有水源的牧场用一根管道相连.

在牧场i中打井的费用是$W_i$ ($1 <= W_i <= 100000$).

把牧场i和j用一根管道相连的费用是$P_{ij}$ ($1 <= P_{ij} <= 100000$,$P_{ij} = P_{ji}$, $P_{ii} = 0$).

请你求出Farmer John最少要花多少钱才能够让他的所有牧场都有水源.

输入格式

• 第$1$行: 一个正整数$N$.

• 第$2~N$+$1$行: 第$i+1$行包含一个正整数$W_i$.

• 第$N+2$~$2N+1$行: 第$N+1+i$行包含$N$个用空格分隔的正整数,第$j$个数表示$P_{ij}$.

输出格式

总共有四个牧场.在$1$号牧场打一口井需要$5$的费用,在$2$或者$3$号牧场打井需要$4$的费用,在$4$号牧场打井需要$3$的费用.在不同的牧场间建立管道需要$2$,$3$或$4$的费用.

input

4

5

4

4

3

0 2 2 2

2 0 3 3

2 3 0 4

2 3 4 0

output

9

输出数据解释

Farmer John需要在$4$号牧场打一口井,然后把所有牧场都用管道连到1号牧场上,总共的花费是$3+2+2+2=9$.

数据规模与约定

时间限制：1s

空间限制：256MB