Description
PIPI是一个商人，经常需要将货物从A地运到B地，我们可以把PIPI经常活动的区域抽象成一个n个结点的地图，用一个nxn的矩阵表示。
矩阵第i行第j列的值代表PIPI从 i 地将货物运到 j 地所需要的固定费用，若该值为-1则代表 i 和 j之间没有直接的通路，注意道路是双向的。
除了上述固定费用外，PIPI在经过每一个结点时都需要交一次过路费(起点和终点不需要交过路费)。
作为一个精打细算的商人，你能帮PIPI计算出从A地到B地的最少费用是多少吗？
Input
第一行输入结点数目n (0<n<=100)
接下来n行输入一个nxn的矩阵(矩阵的值不大于1000)。
第n+2行输入n个数，代表每个结点的过路费cost(cost<=1000)。
第n+3行输入一个数q (q<=10000),代表PIPI的询问次数。
接下来q行，每行输入两个数字，询问A到B的最少花费。
Output
输出q个数字，代表q次询问的结果。若询问的两个地点不可达，输出-1.
Sample Input
5
0 3 22 -1 4
3 0 5 -1 -1
22 5 0 9 20
-1 -1 9 0 4
4 -1 20 4 0
5 17 8 3 1
3
1 3
3 5
2 4