Description

zty到了一座新的城市，开始旅行。该城市是由$n$个路口和$m$条单向通道组成的有向图。zty要进行$q$次旅行，每次从给定标号的路口开始，到给定标号的路口结束。每条道路需要收取一定的过路费，因此，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

【数据规模与约定】

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

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

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