题目背景

Cthugha - USAO

题目描述

给定一张 $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

样例 1 解释

总权值最小的情况是第一个人不走，此时经过点只有 $(2,2)$，所以答案为 $a_{2,2}=5$。

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

15

样例 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$。

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

样例 5 解释

总权值最小的情况是三个人都没有走，权值都为 $a_{1,1}=-1$，答案即为 $-1$。

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

No

样例 6 解释

容易证明最小总权值为负无穷，所以输出 No。

数据范围

本题采用捆绑测试。

子任务编号	$n\times m \leq$	$q\leq$	特殊性质	分值
$1$	$9$		无	$11$
$2$	$10^5$	$1$		$3$
$3$		$50$	A	$24$
$4$	$10^3$		无	$21$
$5$	$10^5$			$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$。