在一个 N×M 个方格组成的棋盘内，有 K 个方格被称为特殊方格。我们要使用一组俄罗斯方块来覆盖这个棋盘，保证特殊方格不能被覆盖，非特殊方格只能被一个俄罗斯方块覆盖，求最多能容纳的俄罗斯方块的数量。
已知有以下三组俄罗斯方块，一个棋盘可能用其中的某一组。
输入格式
第一行三个整数，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子任务
| 测试点 | N,M | K | type |
|---|---|---|---|
| 1∼6 | 0<N,M≤100 | 0≤K≤NM | A |
| 7∼12 | N=M=2L, 0<L≤200000 | K=1 | B |
| 13∼20 | 0<N,M≤11 | 0≤K≤NM | C |