题目描述

有 $n$ 个仓站。任意两个仓站之间都有一条可以直接通行的单向线路，从仓站 $i$ 直接到仓站 $j$ 的费用为 $a_{i,j}$。同一对仓站的两个方向可能费用不同，且 $a_{i,i}=0$。

公司每天都要运输固定的一批货物。第 $i$ 个仓站到第 $j$ 个仓站每天有 $c_{i,j}$ 批货物要送达，每批货物都会选择当前费用总和最小的路线。

接下来有 $q$ 天优惠活动。第 $t$ 天，仓站 $x_t$ 与仓站 $y_t$ 之间的双向直达线路免费，也就是当天把 $a_{x_t,y_t}$ 和 $a_{y_t,x_t}$ 临时改成 $0$。当天结束后，费用恢复原状；不同天之间互不影响。

请对每一天分别求出当天完成所有运输所需的最小总费用。

输入格式

第一行包含两个正整数 $n,q$，表示仓站数量和询问天数。

接下来 $n$ 行，每行 $n$ 个整数，第 $i$ 行第 $j$ 个整数为 $a_{i,j}$。

接下来 $n$ 行，每行 $n$ 个整数，第 $i$ 行第 $j$ 个整数为 $c_{i,j}$。

接下来 $q$ 行，每行两个正整数 $x_t,y_t$，表示这一天免费的一对仓站。保证 $x_t \ne y_t$。

输出格式

输出 $q$ 行。第 $t$ 行输出一个整数，表示第 $t$ 天的最小总费用。

样例一输入

3 3
0 4 2
3 0 6
5 1 0
0 2 1
1 0 2
1 2 0
1 2
2 3
1 3

样例一输出

9
12
13

样例一解释

第一天，$1$ 与 $2$ 之间的直达线路双向免费。重新选择最便宜路线后，总费用为 $9$。

第二天，$2$ 与 $3$ 之间的直达线路双向免费，总费用为 $12$。

第三天，$1$ 与 $3$ 之间的直达线路双向免费，总费用为 $13$。

样例二

见选手目录下的 road/road2.in 与 road/road2.ans。

该样例满足 $20\%$ 的数据范围。

样例三

见选手目录下的 road/road3.in 与 road/road3.ans。

该样例满足 $60\%$ 的数据范围。

样例三

见选手目录下的 road/road4.in 与 road/road4.ans。

该样例满足 $100\%$ 的数据范围。

数据范围

对于 $20\%$ 的数据，$1 \leq n,q \leq 100$。

对于 $60\%$ 的数据，$1 \leq n,q \leq 500$。

对于 $100\%$ 的数据，$1 \leq n \leq 500,1 \leq q \leq 250000,0 \leq a_{i,j} \leq 10^9,0 \leq c_{i,j} \leq 500$。

本题共有$20$ 个测试点，测试点独立计分。