P6234 [eJOI 2019] T形覆盖

如果你玩过俄罗斯方块，应该见过如下图形：  我们称它为一个 ***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```。

#### 输入输出样例 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](https://www.ejoi2019.si) Problem C. [T - Covering](https://www.ejoi2019.si/static/media/uploads/tasks/covering-isc(1).pdf)。 翻译来自：[LibreOJ](https://loj.ac/problem/3197)。