Maximum Tetris Block Placement

You are given an n×m chessboard. There are K special cells on the board (their positions are provided), and these cells must not be covered by any Tetris block. All other (non‑special) cells can be covered by at most one Tetris block.

We want to cover the board with a set of Tetris blocks chosen from one of the following three groups. A test case will indicate which group of pieces to use:

• Group 1: Contains 4 types of tetrominoes – the I‑piece, the O‑piece, the T‑piece and the L‑piece. For example, the base forms (given as sets of 4 cells) are defined as follows (using 0–based coordinates):
  I‑piece: \(\{(0,0),(0,1),(0,2),(0,3)\}\);
  O‑piece: \(\{(0,0),(0,1),(1,0),(1,1)\}\);
  T‑piece: \(\{(0,1),(1,0),(1,1),(1,2)\}\);
  L‑piece: \(\{(0,0),(1,0),(2,0),(2,1)\}\).
  Rotations and reflections of these pieces are allowed, but two placements cannot overlap.
• Group 2: Contains only the O‑piece (the 2×2 square): \(\{(0,0),(0,1),(1,0),(1,1)\}\).
• Group 3: Contains only the I‑piece: \(\{(0,0),(0,1),(0,2),(0,3)\}\) (with rotations allowed).

The task is to determine the maximum number of Tetris blocks that can be placed on the board such that:

• No block covers any special cell.
• No non‑special cell is covered by more than one block.

Note: A block’s shape must appear in one of its allowed rotations/reflections (according to the chosen group). All blocks cover exactly 4 cells.

inputFormat

The first line contains three integers n, m and K (1 ≤ n,m ≤ 8, 0 ≤ K ≤ n*m), denoting the number of rows, columns, and the count of special cells respectively.

Then follow K lines, each line contains two integers r and c (1 ≤ r ≤ n, 1 ≤ c ≤ m) describing the row and column of a special cell.

The last line contains an integer g (1 ≤ g ≤ 3) indicating which group of Tetris blocks to use.

outputFormat

Output a single integer: the maximum number of Tetris blocks that can be placed on the board.

sample

4 4 0

1

1

4