In an $N \times M$ grid, there are $K$ special cells. We want to cover this grid using a set of Tetris-like pieces such that no special cells are covered, and every non-special cell is covered by exactly one piece. Find the maximum number of pieces that can be placed.
It is known that there are three sets of pieces, and a board may use one of these sets.
Input
The first line contains three integers $N, M, K$ and a character $type$, representing the set of pieces used.
The next $K$ lines each contain two integers $X, Y$, representing that the cell at row $X$ and column $Y$ is a special cell.
Output
A single integer representing the answer.
Examples
Input 1
8 8 0 A
Output 1
32
Input 2
7 6 6 C 3 1 3 6 5 3 5 4 5 7 6 7
Output 2
12
Subtasks
| Test Cases | $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 |