【MX-X5-T3】「GFOI Round 1」Cthugha

> [Cthugha - USAO](https://music.163.com/#/song?id=1833853372)

给定一张 $n \times m$ 的网格图，行编号为 $1,2,\dots ,n$，列编号为 $1,2,\dots ,m$。我们用 $(i, j)$ 来描述第 $i$ 行第 $j$ 列的格子。每个格子有一个整数权值 $a_{i,j}$，**注意格子的权值可以是负数**。 给定 $q$ 个人位于网格图上，第 $i$ 个人的初始位置在 $(x_i, y_i)$，**注意不保证每个人初始位置互不相同**。 定义某人**走一步**为：若这个人当前坐标在 $(x,y)$，则将该人移动至 $(x+1,y),(x-1,y),(x,y+1),(x,y-1)$ 其中之一。设移动后到达 $(x^{\prime},y^{\prime})$，此时需要满足 $1\leq x^{\prime}\leq n,1\leq y^{\prime}\leq m$。 在任意时刻，允许任意两个人位于同一个格子。 定义一个人的**权值**为其走若干步后所有经过的格子的权值和（包括起点和终点），注意若一个格子被经过 $k$ 次则其权值需要被累加 $k$ 次。 特别地，若一个人没有走，则其**权值**为其初始位置格子的权值。 定义**总权值**为每个人走若干步数，所有人权值的最大值。 求最终所有人都走到同一个格子的最小**总权值**，或报告不存在最小**总权值**（即最小总权值为负无穷）。

第一行包含三个正整数 $n, m, q$。 接下来 $n$ 行的第 $i$ 行包含 $m$ 个整数 $a_{i, 1}, a_{i, 2}, \ldots, a_{i, m}$。 接下来 $q$ 行的第 $i$ 行包含两个正整数 $x_i, y_i$，表示第 $i$ 个人的初始位置在 $(x _ i, y _ i)$。

若最小总权值不存在（即最小总权值为负无穷），输出 `No`；否则输出一行一个整数表示最小总权值。

3 3 1
1 2 3
4 5 6
7 8 9
2 2

5

3 3 2
1 2 3
4 5 6
7 8 9
2 2
3 3

15

3 3 3
1 4 -3
4 -1 4
7 8 9
1 1
2 2
3 3

10

3 3 9
1 4 -3
4 -1 4
7 8 9
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3

11

3 3 3
-1 4 4
4 -1 4
7 8 -1
1 1
1 1
1 1 

-1

3 3 3
1 4 -5
4 -1 4
7 8 9
1 1
2 2
3 3

No

**【样例解释 #1】** 总权值最小的情况是第一个人不走，此时经过点只有 $(2,2)$，所以答案为 $a_{2,2}=5$。 **【样例解释 #2】** 总权值最小的情况是两个人走到 $(2,3)$，路线分别为 $(2,2)\rightarrow (2,3)$ 和 $(3,3) \rightarrow (2,3)$，答案为 $\max(a_{2,2}+a_{2,3},a_{3,3}+a_{2,3}) = \max(11, 15) = 15$。 **【样例解释 #5】** 总权值最小的情况是三个人都没有走，权值都为 $a_{1,1}=-1$，答案即为 $-1$。 **【样例解释 #6】** 容易证明最小总权值为负无穷，所以输出 `No`。 **【数据范围】** **本题采用捆绑测试。** | 子任务编号 | $n\times m \leq $| $q\leq $ | 特殊性质 | 分值 | | :-: | :-: | :-: | :-: | :-: | | $1$ | $9$ | $9$ | 无 | $11$ | | $2$ | $10^5$ | $1$ | 无 | $3$ | | $3$ | $10^5$ | $50$ | A | $24$ | | $4$ | $10^3$ | $50$ | 无 | $21$ | | $5$ | $10^5$ | $50$ | 无 | $41$ | - 特殊性质 A：$a_{i,j} \geq 1$。 对于所有数据，满足 $1\leq n,m\leq 10^5$，$1\leq n\times m\leq 10^5$，$1\leq q\leq 50$，$1 \le x_i \le n$，$1 \le y_i \le m$，$1\leq |a_{i,j}|\leq 10^9$。