在一个 $N \times 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 \sim 6$ | $0 < N,M \leq 100$ | $0 \leq K \leq NM$ | A |
$7 \sim 12$ | $N=M=2^L,\ 0 < L \leq 200\,000$ | $K=1$ | B |
$13 \sim 20$ | $0 < N,M \leq 11$ | $0 \leq K \leq NM$ | C |