103043: [Atcoder]ABC304 D - A Piece of Cake

Problem Statement

There is a rectangular cake with some strawberries on the $xy$-plane. The cake occupies the rectangular area $\lbrace (x, y) : 0 \leq x \leq W, 0 \leq y \leq H \rbrace$.

There are $N$ strawberries on the cake, and the coordinates of the $i$-th strawberry are $(p_i, q_i)$ for $i = 1, 2, \ldots, N$. No two strawberries have the same coordinates.

Takahashi will cut the cake into several pieces with a knife, as follows.

• First, cut the cake along $A$ different lines parallel to the $y$-axis: lines $x = a_1$, $x = a_2$, $\ldots$, $x = a_A$.
• Next, cut the cake along $B$ different lines parallel to the $x$-axis: lines $y = b_1$, $y = b_2$, $\ldots$, $y = b_B$.

As a result, the cake will be divided into $(A+1)(B+1)$ rectangular pieces. Takahashi will choose just one of these pieces to eat. Print the minimum and maximum possible numbers of strawberries on the chosen piece.

Here, it is guaranteed that there are no strawberries along the edges of the final pieces. For a more formal description, refer to the constraints below.

Constraints

• $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$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$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$

Output

Print the minimum possible number of strawberries $m$ and the maximum possible number $M$ on the chosen piece in the following format, separated by a space.

$m$ $M$

Sample Input 1

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

Sample Output 1

0 2

There are nine pieces in total: six with zero strawberries, one with one strawberry, and two with two strawberries. Therefore, when choosing just one of these pieces to eat, the minimum possible number of strawberries on the chosen piece is $0$, and the maximum possible number is $2$.

Sample Input 2

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

Sample Output 2

1 1

Each piece has one strawberry on it.

问题描述

在二维平面直角坐标系$xy$上有一个矩形蛋糕，上面放了一些草莓。蛋糕占据了矩形区域$\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将用刀将蛋糕沿着以下方式切割成几块：

• 首先沿着$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)$个矩形块。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$。

$m$ $M$

样例输入1

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

样例输出1

0 2

总共有九块：六块上面有0个草莓，一块上面有1个草莓，两块上面有2个草莓。因此，当只选择其中一块来吃时，所选块上草莓的最小可能数量为$0$，最大可能数量为$2$。

样例输入2

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

样例输出2

1 1

每块上面都有一颗草莓。