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

---

【题目描述】

　　小H的花园里有 \(N\) 棵栀子花树，编号为 1 到 \(N\)，他决定给每棵树浇水，他可以直接在一棵旁边直接挖一口井来获得水，也可以用管子从任意有水的树那里来获得水。

　　在第 \(i\) 颗树旁边挖一口井的代价为 \(W_i\)，用管子连接第 \(i\) 与第 \(j\) 颗树的代价为 \(P_{ij}\) 。请求出小H浇灌这些树花费的最小代价。

【输入格式】

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

【输出格式】

　　仅一行，小H浇灌这些树的最小代价。

【输入输出样例】

　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。

【数据限制】

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

【来源】

　　Mr.he