Description

王国最近被敌对国家攻击了！众所周知，战争时期最需要破坏的就是通讯和粮草。 现在所有道路都已经被破坏了，王国的 n 个城市（编号为 1 ~ n）都处于孤立无援的状态 为了修复所有城市的通讯，使得国王下达的命令可以传递到所有城市 现在国王希望在某些城市建立 军事基地，在第 i 个城市建立 军事基地 所需要花费是 ai，军事基地 可以通过卫星直接接收到国王下达的命令 因为建立军事基地的花费比较大，也可以通过修复道路来使得两个城市可以传递信息 现在已知修复两个城市 i,j 之间道路需要的花费为 v{i,j}，并且这条道路是双向道路 现在因为正处于战争时期，所以资金非常紧张，王国希望以最小的花费使得他的命令可以传递到所有城市 注意：国王不处于任何城市之中，所以所有城市中至少要建立一个 军事基地 来接收信息

Format

Input

输入第一行包含一个整数 n,表示城市个数 接下来 n 行，第 i 个数 ai 表示第 i 座城市建立 军事基地 所需要的花费 接下来一个 n * n 的矩阵 v，其中 v{i,j} 表示在第 i 座城市和第 j 座城市修复道路所需要的花费

Output

输出仅包含一个整数，表示最小花费

Samples

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

9

Limitation

题目保证 v{i,j} = v{j,i} 且 v{i,i} = 0 对于 40% 的数据 1 <= n <= 50 对于 100% 的数据，1 <= n <= 300, 0 <= ai,v{i,j} <= 100000