AT_abc304_d [ABC304D] A Piece of Cake

题目描述

在 $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)$ 块长方形，现在高桥要选择其中一块，求他选择的蛋糕上草莓个数可能的最大值和最小值。

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

输入格式

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

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

第二行一个整数 $N$。

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

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

接下来一行 $A$ 个整数 $a_1,a_2,\cdots,a_A$。

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

接下来一行 $B$ 个整数 $b_1,b_2,\cdots,b_B$。

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

输出格式

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

输入输出样例 #1

输入 #1

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

输出 #1

0 2

输入输出样例 #2

输入 #2

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

输出 #2

1 1

说明/提示

• $3 \le W, H \le 10^9$
• $1 \le N \le 2 \times 10^5$
• $0 < p_i < W$
• $0 < q_i < H$
• $i \ne j \implies (p_i, q_i) \ne (p_j, q_j)$
• $1 \le A, B \le 2 \times 10^5$
• $0 < a_1 < a_2 <\cdots < a_A < W$
• $0 \lt b_1 \lt b_2 \lt \cdots \lt b_B \lt H$
• $p_i \notin \{ a_1, a_2, \ldots, a_A \}$
• $q_i \notin \{ b_1, b_2, \ldots, b_B \}$
• 所有输入的值都是正整数。