题目描述

$xy$ -平面上にいくつかのイチゴが載った長方形のケーキがあります。 ケーキは、長方形領域 $ \lbrace\ (x,\ y)\ :\ 0\ \leq\ x\ \leq\ W,\ 0\ \leq\ y\ \leq\ H\ \rbrace $ をちょうど占めます。

ケーキには $N$ 個のイチゴが載っており、$i\ =\ 1,\ 2,\ \ldots,\ N$ について、$i$ 番目のイチゴの座標は $(p_i,\ q_i)$ です。 $2$ 個以上のイチゴが同一の座標にあることはありません。

高橋君は、このケーキを包丁で下記の通りにいくつかのピースに切り分けます。

• まず、ケーキを通る $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)$ 個の長方形のピースに分割されます。 高橋君はそれらのうちのいずれか $1$ 個だけを選んで食べます。 高橋君が選んだピースに載っているイチゴの個数としてあり得る最小値と最大値をそれぞれ出力してください。

ここで、最終的にピースの縁となる位置にはイチゴが存在しないことが保証されます。 より形式的な説明は下記の制約を参照してください。

输入格式

入力は以下の形式で標準入力から与えられる。

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

题目大意

题目描述

在 $xy$-平面上，一块带有一些草莓的蛋糕占据了一块矩形区域 $\{(x,y):0\le x\le W,0\le y\le H\}$。

蛋糕上有 $N$ 个草莓，第 $i$ 个草莓的坐标是 $(p_i,q_i)$。现在，高桥要用小刀按照以下规则将蛋糕切成小块。

• 首先，沿着平行于 $y$ 轴的 $A$ 条直线：直线 $x=a_1$、直线 $x=a_2$、……、直线 $x=a_A$，将蛋糕切开。
• 接着，沿着平行于 $x$ 轴的 $Y$ 条直线：直线 $y=b_1$、直线 $y=b_2$、……、直线 $y=b_B$，将蛋糕切开。

到了最后，蛋糕会被切成 $(A+1)(B+1)$ 块长方形，现在高桥要选择其中一块，求他选择的蛋糕上草莓个数可能的最大值和最小值。

保证切割的边缘线上没有草莓，具体请参照数据范围。

输入格式

输入共 $(6+N)$ 行。

第一行两个整数 $W,H$。

第二行一个整数 $N$。

第 $3\sim N+2$ 行，第 $i+2$ 行两个整数 $p_i,q_i$。

第 $N+3$ 行，一个整数 $A$。

接下来一行 $A$ 个整数 $a_1$，$a_2$，……，$a_A$。

第 $N+5$ 行，一个整数 $B$。

接下来一行 $B$ 个整数 $b_1$，$b_2$，……，$b_B$。

以上变量含义均参考题意。

输出格式

共一行用空格隔开的两个整数，第一个表示可能的最少的草莓数量，第二个表示可能的最多的草莓数量。

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

0 2

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

1 1

提示

制約

• $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 $
• 入力はすべて整数

Sample Explanation 1

全 $9$ 個のピースの内訳は、イチゴが $0$ 個載ったものが $6$ 個、イチゴが $1$ 個載ったものが $1$ 個、イチゴが $2$ 個載ったものが $2$ 個です。 よって、それらのうちのいずれか $1$ 個だけを選んで食べるとき、選んだピースに載っているイチゴの個数としてあり得る最小値は $0$ 、最大値は $2$ です。

Sample Explanation 2

どのピースにもイチゴが $1$ 個載っています。