题目描述

唐僧师徒四人在西天取经的过程中，少不了土地公公的帮忙，通常都是孙悟空剁剁脚土地公公就出来。土地公公是负责掌管一方土地的正神，这天土地公公决定给他管辖的N（1<=N<=300）块土地引入水源，他可以通过在土地上打一口井或通过管道将土地连接到另一块已经有水源的土地。
在土地i挖井的成本为W_i（1<=W_i<=100000）。
连接 i 块土地与 j 块土地要 Pij（1≤Pij≤10^5，且 Pji=Pij）元。
如果要使所有土地都引入水源，请求出土地公公最少需要花费多少钱。

输入格式：

第1 行为一个整数n。
第2 到n+1行每行一个整数，从上到下分别为W_1到W_n。
第n+2 到2n+1 行为一个矩阵，表示连接 i 块土地与 j 块土地要 Pij元。

输出格式：

只有一行，为一个整数，表示土地公公最少需要花费多少钱。

输入样例#1：

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

输出样例#1：

9