题目背景

扶苏经常坐飞机旅行。对于从 $A$ 地到达 $B$ 地的旅行需求，共有两种方法可以解决，一是直接乘坐从 $A$ 地飞往 $B$ 地的飞，称为直飞；另一种是从 $A$ 地飞往另一个中间城市 $C$，再从 $C$ 飞往 $B$，称为经 $C$ 地中转。有时，从中间城市中转的价格比直飞更便宜。

题目描述

某航司的航线覆盖了 $n$ 个城市。城市从 $1$ 到 $n$ 编号。两个城市之间可能有航线，也可能没有航线。一条航线可能会有两种票价，一是普通经济舱票价 Y，二是中转折扣票价 T。一些航线可能只有普通经济舱而不售卖中转折扣票。

对于从城市 $u$ 出发，到达城市 $v$ 的单向航线，用 $Y_{u,v}$ 表示这条航线的普通经济舱票价，$T_{u,v}$ 表示这条航线的中转折扣票价。航线是单向的意味着：

1. 可能 $u$ 到 $v$ 有航线，但是 $v$ 到 $u$ 没有航线；
2. 可能 $T_{u,v} \neq T_{v,u}$，可能 $Y_{u,v} \neq Y_{v,u}$。

扶苏共有 $q$ 个旅行计划，每个计划有一个出发城市 $u$ 和一个到达城市 $v$，她将从城市 $u$ 出发，前往城市 $v$。她有两种选择：

1. 如果 $u$ 到 $v$ 有直飞的航线，可以花费 $Y_{u,v}$ 购买普通经济舱机票前往 $v$。
2. 选择另一个城市 $w$，使得 $u$ 到 $w$、$w$ 到 $v$ 均有中转折扣票售卖，然后花费 $T_{u,w} + T_{w,v}$ 元购买两程中转折扣票，经 $w$ 地中转到达 $v$。

扶苏会选择两种方案中花费较小的方案。当然，如果只有其中一种方案可用，她会选择该方案。

现在，给定飞机每条航线的机票价格，你要对每个旅行计划求出花费最小的方案的花费。

输入格式

第一行是两个整数，表示城市数量 $n$ 和计划数量 $q$。
接下来 $n$ 行，每行 $n$ 个整数，表示普通经济舱票价。第 $i$ 行的第 $j$ 个整数表示城市 $i$ 飞往城市 $j$ 的普通经济舱票价 $Y_{i,j}$。如果 $i$ 到 $j$ 没有航线，则 $Y_{i,j} = -1$。
接下来 $n$ 行，每行 $n$ 个整数，表示中转折扣票价。第 $i$ 行的第 $j$ 个整数表示城市 $i$ 飞往城市 $j$ 的中转折扣票价 $T_{i,j}$。如果 $i$ 到 $j$ 没有航线或不售卖中转折扣票，则 $T_{i,j} = -1$。
接下来 $q$ 行，每行两个整数 $u,v$，表示一个飞行计划。

输出格式

对于每个飞行计划，输出一行一个整数表示最小的花费。
如果该计划从 $u$ 无论如何无法到达 $v$，输出 $-1$。

3 3
-1 5 10
15 -1 5
5 10 -1
-1 3 -1
-1 -1 1
-1 -1 -1
1 3
1 2
2 1

4
5
15

提示

对全部的测试数据，保证 $3 \leq n \leq 100$，$1 \leq q \leq 1000$，$-1 \leq Y_{i,j}, T_{i,j} \leq 10^9$，$T_{i,i} = Y_{i,i}= -1$。$1 \leq u,v \leq n$，$u \neq v$。数据保证若 $Y_{i,j} = -1$ 则 $T_{i,j} = -1$。