题目描述

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

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

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

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

输入格式

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

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

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

输出格式

最小的危险指数和．

样例

输入样例

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

输出样例

7

提示

输入详细信息：

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

输出详细信息：

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