#2706. [SDOI2012]棋盘覆盖

内存限制:256 MiB 时间限制:10 Sec

题目描述

在一个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<=N*M

A

[7, 12]

N=M=2^L,0<L<=200000

K=1

B

[13, 20]

0<N,M<=11

0<=K<=N*M

C

 

 

样例

样例输入


			

样例输出


			

数据范围与提示