Description

One day, linyorson created an $n \times n$ square grid in Minecraft. He has $m$ torches and $k$ glowstones, placed at positions $(x_1, y_1)$ through $(x_m, y_m)$ and $(o_1, p_1)$ through $(o_k, p_k)$, respectively. Any cell that has no light and has nothing placed on it will spawn monsters. How many cells in this grid will spawn monsters?

Note: In this problem the illumination ranges of torches and glowstone are different from the original Minecraft. Please follow the description given here.

P.S. The illumination range of a torch is:

Glowstone:

Input Format

There are $m + k + 1$ lines in total.
The first line contains $n, m, k$.
Lines $2$ through $m + 1$ give the positions of torches $x_i, y_i$.
Lines $m + 2$ through $m + k + 1$ give the positions of glowstones $o_i, p_i$.

Note: There may be no glowstone, but there is at least one torch.

Output Format

Output the number of cells that will spawn monsters.

5 1 0
3 3

12

Hint

Constraints: $1 \le n \le 100$, $1 \le m + k \le 25$, $1 \le m \le 25$, $0 \le k \le 5$.

Translated by ChatGPT 5