{"raw_statement":[{"iden":"background","content":"\n扶苏经常坐飞机旅行。对于从 $A$ 地到达 $B$ 地的旅行需求，共有两种方法可以解决，一是直接乘坐从 $A$ 地飞往 $B$ 地的飞，称为直飞；另一种是从 $A$ 地飞往另一个中间城市 $C$，再从 $C$ 飞往 $B$，称为经 $C$ 地中转。有时，从中间城市中转的价格比直飞更便宜。"},{"iden":"statement","content":"\n某航司的航线覆盖了 $n$ 个城市。城市从 $1$ 到 $n$ 编号。两个城市之间可能有航线，也可能没有航线。一条航线可能会有两种票价，一是普通经济舱票价 Y，二是中转折扣票价 T。一些航线可能只有普通经济舱而不售卖中转折扣票。\n\n对于从城市 $u$ 出发，到达城市 $v$ 的**单向**航线，用 $Y_{u,v}$ 表示这条航线的普通经济舱票价，$T_{u,v}$ 表示这条航线的中转折扣票价。航线是单向的意味着：\n\n1. 可能 $u$ 到 $v$ 有航线，但是 $v$ 到 $u$ 没有航线；\n2. 可能 $T_{u,v} \\neq T_{v,u}$，可能 $Y_{u,v} \\neq Y_{v,u}$。\n\n扶苏共有 $q$ 个旅行计划，每个计划有一个出发城市 $u$ 和一个到达城市 $v$，她将从城市 $u$ 出发，前往城市 $v$。她有两种选择：\n\n1. 如果 $u$ 到 $v$ 有直飞的航线，可以花费 $Y_{u,v}$ 购买普通经济舱机票前往 $v$。\n2. 选择另**一个**城市 $w$，使得 $u$ 到 $w$、$w$ 到 $v$ 均有中转折扣票售卖，然后花费 $T_{u,w} + T_{w,v}$ 元购买两程中转折扣票，经 $w$ 地中转到达 $v$。\n\n扶苏会选择两种方案中花费较小的方案。当然，如果只有其中一种方案可用，她会选择该方案。\n\n现在，给定飞机每条航线的机票价格，你要对每个旅行计划求出花费最小的方案的花费。"},{"iden":"input","content":"\n第一行是两个整数，表示城市数量 $n$ 和计划数量 $q$。  \n接下来 $n$ 行，每行 $n$ 个整数，表示普通经济舱票价。第 $i$ 行的第 $j$ 个整数表示城市 $i$ 飞往城市 $j$ 的普通经济舱票价 $Y_{i,j}$。如果 $i$ 到 $j$ 没有航线，则 $Y_{i,j} = -1$。  \n接下来 $n$ 行，每行 $n$ 个整数，表示中转折扣票价。第 $i$ 行的第 $j$ 个整数表示城市 $i$ 飞往城市 $j$ 的中转折扣票价 $T_{i,j}$。如果 $i$ 到 $j$ 没有航线或不售卖中转折扣票，则 $T_{i,j} = -1$。  \n接下来 $q$ 行，每行两个整数 $u,v$，表示一个飞行计划。"},{"iden":"output","content":"\n\n对于每个飞行计划，输出一行一个整数表示最小的花费。  \n如果该计划从 $u$ 无论如何无法到达 $v$，输出 $-1$。"},{"iden":"note","content":"| 测试点编号 | $n \\leq$ | 特殊约定 |\n| :-:| :-:| :-:|\n| $1,2$ | $3$ | 无 |\n| $3,4,5$ | $100$ | $T_{i,j} = -1$|\n| $6,7$ | $100$ | $T_{i,j} \\neq -1$（对 $i\\neq j$）|\n| $8,9,10$ | $100$ | 无 |\n\n对全部的测试数据，保证 $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$。"}],"translated_statement":null,"sample_group":[["3 3\n-1 5 10\n15 -1 5\n5 10 -1\n-1 3 -1\n-1 -1 1\n-1 -1 -1\n1 3\n1 2\n2 1","4\n5\n15"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}