Score : $400$ points

问题描述

在 $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$。没有两颗草莓具有相同的坐标。

高桥将会用刀将蛋糕切成几块，方法如下：

• 首先，沿平行于 $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)$ 个矩形小块。高桥将从中选择一块来吃。请输出所选蛋糕块上可能包含的最少和最多草莓数量。

这里保证最终每块蛋糕边缘上没有草莓。更正式的描述，请参考以下约束条件。

以上为通义千问 qwen-max 翻译，仅供参考。

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.

update @ 2024/3/10 08:34:01