题目描述

如果你玩过俄罗斯方块，应该见过如下图形：

我们称它为一个 T 形四格拼板 。其 中心 被标记为 $\times$。

Manca 画了一个 $n$ 行 $m$ 列的长方形网格。行从 $0$ 至 $m-1$ 编号，列从 $0$ 至 $n-1$ 编号。她将网格中的一些格子标记为 特殊格子 。然后，她想要她的朋友 Nika 帮助她将 T 形四格拼板按找如下规则摆放：

• 特殊格子的数量与 T 形四格拼板的数量相同，每个 T 形四格拼板的中心在网格上的位置必须是特殊格子。
• T 形四格拼板之间不能有重叠部分。
• 所有拼板的部分均在网格内。

注意，T 形四格拼板有四种摆放方式：$\bot \top \vdash \dashv$。

如果方案不存在，输出 No，否则请找出一种方案使得被拼板覆盖的数总和最大，求出这个最大值。

输入格式

第一行两个整数 $m,n$ 分别表示行数和列数。

接下来 $m$ 行，每行 $n$ 个整数，第 $i$ 行第 $j$ 个数（从 $0$ 开始编号）表示方格中第 $i$ 行第 $j$ 列的数 $a_{i,j}$。

接下来一行，一个整数 $k$ ，表示特殊格子的数量。

接下来 $k$ 行，每行两个整数 $r_i,c_i$，表示第 $i$ 个被标记的特殊格子的位置。

输出格式

如果有方案，输出可能的被覆盖的格子内数总和的最大值，否则输出 No。

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

67

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

No

提示

输入输出样例 1 解释

其中一种最优的方案如下：

• $(1,1)$ 位置的摆放方式为 $\dashv$。
• $(2,2)$ 位置的摆放方式为 $\vdash$。
• $(3,4)$ 位置的摆放方式为 $\bot$。

数据规模与约定

本题采用多测试点捆绑测试，共有 7 个子任务。

• Subtask 1（5 points）：$k\le 10^3$，保证对于所有 $i\ne j$，$\max(|r_i-r_j|,|c_i-c_j|)>2$。
• Subtask 2（10 points）：$k\le 10^3$，保证对于所有 $i\ne j$，若 $\max(|r_i-r_j|,|c_i-c_j|)\le 2$，则 $(r_i,c_i)$ 与 $(r_j,c_j)$ 有邻边。
• Subtask 3（10 points）：$k\le 10^3$，保证对于所有 $i\ne j$，$\max(|r_i-r_j|,|c_i-c_j|)\ne 2$。
• Subtask 4（10 points）：所有特殊格子在同一行。
• Subtask 5（15 points）：$k\le 10$。
• Subtask 6（20 points）：$k\le 10^3$
• Subtask 7（30 points）：无其他限制。

对于所有数据，满足：$1\le k\le nm\le 10^6,a_{ij}\in[0,10^3],r_i\in[0,m),c_i\in[0,n)$。

说明

原题来自：eJOI2019 Problem C. T - Covering。

翻译来自：LibreOJ。