时间限制：1秒　　内存限制：256M

---

【题目描述】

　　金紫观村的饮水问题一直困扰着村民，政府部门决心彻底解决这个问题!已知村里共有 \(N\) 户人家，编号为 \(1\) 到 \(N\)，每户人家的饮用水可以有两种方式解决：
　　1、可直接在一户人家旁边挖一口井。在第i户人家旁边挖一口井的代价为 \(A_i\)；
　　2、也可以用水管从任意有水的人家那里来获取水。用管子连接第 \(i\) 与第 \(j\) 户人家的代价为 \(B_{ij}\)。
　　政府想知道，让所有人家都有饮水最少花费是多少？

【输入格式】

　　输入的第一行是一个整数 \(N\)。第二行到第 \(N+1\) 行，行 \(i+1\) 表示 \(A_i\)。第 \(N+2\) 行到第 \(2N+1\) 行，行 \(N+1+i\) 包含 \(N\) 个用空格分隔开来的整数，每行第 \(j\) 个数字即是 \(B_{ij}\) \((B_{ij}=B_{ji}\)，且 \(B_{ii}=0)\)。

【输出格式】

　　输出仅一行一个整数，表示最小花费。

【输入输出样例1】

　Input

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

　Output

9

【输入输出样例解释】

　　在第 4 户人家旁挖一口井，然后 1 从 4 引水管，2 和 3 从 1 各引一根水管，总代价为：3 + 2 + 2 + 2 = 9。

【输入输出样例2】

　Input

10
537
914
269
536
882
245
172
615
367
688
0 56 91 16 53 82 30 52 51 51
56 0 36 24 12 41 67 50 37 99
91 36 0 96 6 34 2 60 74 58
16 24 96 0 25 27 8 79 34 14
53 12 6 25 0 12 23 30 44 7
82 41 34 27 12 0 79 68 87 66
30 67 2 8 23 79 0 39 32 14
52 50 60 79 30 68 39 0 57 38
51 37 74 34 44 87 32 57 0 1
51 99 58 14 7 66 14 38 1 0

　Output

266

【数据限制】

　　对于 \(100\%\) 的数据，\(1≤N≤1000\)，\(1≤A_i,B_{ij}≤100000\)。

【来源】

　　Mr.he