该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

ない

题目描述

• 给定一张 $n$ 行 $m$ 列的网格图，为了方便，我们约定 $(x_{i},y_{i})$ 表示网格图第 $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$ 次。
• 特别地，若一个人没有走，则其权值为其初始位置格子的权值。
• 定义总权值为每个人走若干步数，所有人权值的最大值，而不是求和。
• 求最终所有人都走到同一个格子的最小总权值，或报告不存在最小总权值（即最小总权值为负无穷）。

输入格式

从 dis.in 读入。

• 第一行包含三个正整数 $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)$。

输出格式

输出到 dis.out。

• 输出一行一个整数表示最小总权值，
• 特别地，若最小总权值不存在（即最小总权值为负无穷），输出 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。

数据范围

• $1\leq n,m\leq 10^5$
• $1\leq n 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$

子任务

• 大样例下载
• 编号为 $i$ 的大样例满足编号为 $i$ 的子任务的限制