#123. 旅行

旅行

Description

zty到了一座新的城市,开始旅行。该城市是由nn个路口和mm条单向通道组成的有向图。zty要进行qq次旅行,每次从给定标号的路口开始,到给定标号的路口结束。每条道路需要收取一定的过路费,因此,zty一定会沿着最短路前行

经过每个路口时,也会有相应的通行费用。但奇怪的是,zty这次旅行的费用为:所经过的路径的花费之和,加上该路径上经过路口(包括起点和终点)中收费的最大值。

zty想知道,其完成这次旅行的最小花费是多少?

Format

Input

第一行两个正整数n,q,其含义见题目描述。

第二行n个非负整数,表示每个点的通行费用。

接下来是一个n*n的矩阵,第i行第j列表示i到j的每条边的通行费用,保证a[i][i]=0。

接下来q行每行两个正整数x,y(x≠y)表示询问x到y的最小花费。

Output

输出共q行,对于每次询问,输出该次旅行的最小花费。

Samples

5 2
2 5 3 4 4
0 3 2 10 10
3 0 10 3 3
10 10 0 4 1
10 3 4 0 1
10 3 1 1 0
2 3
1 4
9
8

Limitation

【输入输出样例解释】

对于第一个询问我们可以走2->5->3。答案为3+1+max{5,4,3}=9

对于第二个询问我们可以走1->3->5->4。答案为2+1+1+max{2,3,4,4}=8

【数据规模与约定】

image

特殊性质1:每个路口的通行费用都为0。

特殊性质2:除n号路口外每个路口的通行费用都为0。

0≤道路、路口的通行费用≤10000