Comet OJ

C0927 [SDOI2012]棋盘覆盖

内存限制：256 MB 时间限制：1000 ms

题目描述

在一个 $N \times M$ 个方格组成的棋盘内，有 $K$ 个方格被称为特殊方格。我们要使用一组俄罗斯方块来覆盖这个棋盘，保证特殊方格不能被覆盖，非特殊方格只能被一个俄罗斯方块覆盖，求最多能容纳的俄罗斯方块的数量。

已知有以下三组俄罗斯方块，一个棋盘可能用其中的某一组。

image.png

输入格式

第一行三个整数，$N,M,K$，和一个字符，$type$，为所用的俄罗斯方块组。

接下来 $K$ 行每行两个整数，$X,Y$，表示第 $X$ 行第 $Y$ 列为特殊方格。

输出

一个整数，为所求的答案。

样例

样例输入 1

8 8 0 A

样例输出 1

32

样例输入 2

7 6 6 C
3 1
3 6
5 3
5 4
5 7
6 7

样例输出 2

12

提示

$\begin{array}{|c|c|c|c|}\hline 测试点 & N,M & K & type \\ \hline [1,6] & 0 < N,M \le 100 & 0 \le K \le N \times M & A \\ \hline [7,12] & N=M=2^L,0 < L \le 200000 & K=1 & B \\ \hline [13,20] & 0 < N,M \le 11 & 0 \le K \le N \times M & C \\ \hline \end{array}$