春游的时间到了，CC想要利用这个难得的好时间去旅游。

CC有N个想要去的旅游景点，他想要在这个寒假全部都去玩一次，经过他的调查，他已经得到了任何两个旅游景点之间的路费。所以他想让你帮他设计一条旅行路线，使得最终的费用最小。

 

输入文件第一行包含一个正整数N，表示CC想要去的旅游景点的个数。

接下来一行包含N个正整数，分别表示从CC家到这些旅游景点的路费。

接下来N行，每行N个正整数，第i行第j个数表示从第i个景点到第j个景点的路费。

 

输出文件包含仅一行，为CC从家里出发到这N个旅游景点旅游后再回到家的最低路费

 

对于40%的数据，N ≤ 10。 对于100%的数据，N ≤ 20。 输入数据为无向图，且满足三角不等式，即对于任意两个点，从A到B的边和从B到A的边的长度相等，且他们之间的最短距离就是他们直接相连的边的长度。