当前没有测试数据。

D - 一块蛋糕

得分：400分

问题描述

有一个矩形蛋糕，上面有一些草莓。蛋糕占据了矩形区域 $\lbrace (x, y) : 0 \leq x \leq W, 0 \leq y \leq H \rbrace$。

蛋糕上有 $N$ 个草莓，第$i$个草莓的坐标是 $(p_i, q_i)$，其中 $i = 1, 2, \ldots, N$。没有两个草莓有相同的坐标。

Takahashi 将用刀将蛋糕切成几块，具体如下：

• 首先，沿着与 $y$-轴平行的 $A$ 条不同线切割：$x = a_1$，$x = a_2$，$\ldots$，$x = a_A$。
• 然后，沿着与 $x$-轴平行的 $B$ 条不同线切割：$y = b_1$，$y = b_2$，$\ldots$，$y = b_B$。

结果是，蛋糕被分成 $(A+1)(B+1)$ 小块。Takahashi 将选择其中的一块来吃。请输出这个蛋糕块上可能的草莓数量的最小值和最大值。

注意，保证最终蛋糕的边上不会有草莓。更详细的描述请参见下面的约束条件。

约束条件

• $3 \leq W, H \leq 10^9$
• $1 \leq N \leq 2 \times 10^5$
• $0 \lt p_i \lt W$
• $0 \lt q_i \lt H$
• $i \neq j \implies (p_i, q_i) \neq (p_j, q_j)$
• $1 \leq A, B \leq 2 \times 10^5$
• $0 \lt a_1 \lt a_2 \lt \cdots \lt a_A \lt W$
• $0 \lt b_1 \lt b_2 \lt \cdots \lt b_B \lt H$
• $p_i \not \in \lbrace a_1, a_2, \ldots, a_A \rbrace$
• $q_i \not \in \lbrace b_1, b_2, \ldots, b_B \rbrace$
• 所有输入的值都是整数。

---

输入

从标准输入读入数据，格式如下：

$W$ $H$

$N$

$p_1$ $q_1$

$p_2$ $q_2$

$\vdots$

$p_N$ $q_N$

$A$

$a_1$ $a_2$ $\ldots$ $a_A$

$B$

$b_1$ $b_2$ $\ldots$ $b_B$

输出

输出选择的蛋糕块可能的草莓数量的最小值和最大值。格式如下，用一个空格分隔：

``` $m$ $M$ ```

---

7 6
5
6 1
3 1
4 2
1 5
6 2
2
2 5
2
3 4

0 2

一共有九个蛋糕块：六块上没有草莓，一块上有一个草莓，两块上有两个草莓。所以，当选择其中一块来吃时，这块蛋糕上可能的草莓数量的最小值为 $0$，最大值为 $2$。

---

4 4
4
1 1
3 1
3 3
1 3
1
2
1
2

1 1

每块蛋糕上都有一个草莓。