切蛋糕

题目描述

在 $xy$ 平面上有一块长方形的蛋糕,上面放有一些草莓。蛋糕占据矩形区域 $\lbrace (x, y) : 0 \le x \le W, 0 \le y \le H \rbrace$。

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

高桥用刀将蛋糕切成若干块,方法如下。

首先,沿着 $A$ 条不同的平行于 $y$ 轴的直线切蛋糕:直线 $x = a_1$,$x = a_2$,$\ldots$,$x = a_A$。

接着,沿着 $B$ 条不同的平行于 $x$ 轴的直线切蛋糕:直线 $y = b_1$,$y = b_2$,$\ldots$,$y = b_B$。

这样,蛋糕被分成 $(A+1)(B+1)$ 块矩形。高桥将只选择其中一块来吃。请输出选中的那一块上可能有的草莓数量的最小值和最大值。

这里,保证任何草莓都不在最终小块的边界上。更正式的描述请参照数据范围。

输入格式

输入按以下格式从标准输入给出:

W H
N
p_1 q_1
p_2 q_2
⋮
p_N q_N
A
a_1 a_2 … a_A
B
b_1 b_2 … b_B

输出格式

以空格分隔输出选中的小块上可能有的草莓数量的最小值 $m$ 和最大值 $M$,格式如下。

m M

样例

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

0 2

总共有九块:六块有 0 颗草莓,一块有 1 颗草莓,两块有 2 颗草莓。因此,只选择其中一块来吃时,选中的那块上草莓数量的最小值为 $0$,最大值为 $2$。

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

1 1

每块上恰好有一颗草莓。

数据范围

• $3 \le W, H \le 10^9$
• $1 \le N \le 2 \times 10^5$
• $0 \lt p_i \lt W$
• $0 \lt q_i \lt H$
• 当 $i \neq j$ 时,$(p_i, q_i) \neq (p_j, q_j)$
• $1 \le A, B \le 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 \notin \lbrace a_1, a_2, \ldots, a_A \rbrace$
• $q_i \notin \lbrace b_1, b_2, \ldots, b_B \rbrace$
• 所有输入值均为整数。