题目描述

农夫约翰正驾驶一条小艇在牛勒比海上航行．

海上有$\red{N(1≤}$$\red{N≤}$$\red{100)}$个岛屿，用$\red{1}$到$\red{N}$编号．约翰从$\red{1}$号小岛出发，最后到达$\red{N}$号小岛．一张藏宝图上说，如果他的路 程上经过的小岛依次出现了$\red{Ai，}$$\red{A2，}$…，$\red{AM(2≤}$$\red{M≤}$$\red{10000)}$这样的序列（不一定相邻），那他最终就能找到古老的宝藏．

但是，由于牛勒比海有海盗出没．约翰知道任意两个岛屿之间的航线上海盗出没的概率，他用一个危险指数$\red{Dij(0≤}$$\red{Dij≤}$$\red{100000)}$来描述．他希望他的寻宝活动经过的航线危险指数之和最小．

那么，在找到宝藏的前提下，这个最小的危险指数是多少呢？

输入格式

第$\red{1}$行输入$\red{N}$和$\red{M，}$之后$\red{M}$行一行一个整数表示$\red{A}$序列，

之后输入一个$\red{N\times N}$的方阵，表示两两岛屿之间航线的危险指数．

数据保证$\red{Dij=Dji，}$$\red{Dii=0}$．

输出格式

最小的危险指数和．

样例

输入样例

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

输出样例

7

提示

输入详细信息：

有$\red{3}$个岛屿，藏宝图要求农民约翰按顺序访问$\red{4}$个岛屿：岛$\red{1}$、岛$\red{2}$、岛$\red{1，}$最后是岛$\red{3}$。给出了路径的危险等级 ：路径$\red{（1，}$$\red{2）}$；$\red{(2, 3)}$; $\red{（3，}$$\red{1）}$和反向路径的危险等级分别为$\red{5}$、$\red{2}$和$\red{1}$。

输出详细信息：

他可以通过旅行获得总危险度为$\red{7}$的宝藏岛$\red{1}$、$\red{3}$、$\red{2}$、$\red{3}$、$\red{1}$和$\red{3}$的顺序。$\red{cow}$地图的要求$\red{（1}$、$\red{2}$、$\red{1}$和$\red{3）}$对此路线满意。我们避开这条路岛屿$\red{1}$和$\red{2}$之间，因为其危险等级较高。