Logo Daimayuan Online Judge

Home

时间限制:1 s 空间限制:1024 MB

#853. 矩形划分

附加文件 统计

给定一个左下角位于 $(0 , 0)$ 右上角位于 $(n , m)$ 的矩形 , 矩形的四条边都与坐标轴平行 , 你需要将它划分成尽可能多的块数。

划分的规则如下:

  1. 每次会给出两个点 $p , q$ , 你需要在点 $p , q$ 之间连一条线来划分矩形 , 保证 $p , q$ 分别在矩形的一组对边上 , 即要么分别在左右边界上 , 要么分别在上下边界上。
  2. 连的线并不要求是直线 , 可以是曲线 , 但不能与自己有交点 , 不能与矩形边界有除 $p , q$ 以外的交点。
  3. 两条线最多有一个交点 , 如果有交点 , 那么一定是在交点处交叉。
  4. 线的两端在同一组对边上的线互不相交
  5. 保证给出的所有点两两不同

输出最多可以划分多少块。

输入格式

第一行两个整数 $n,m$ , 含义如题面所示。 $(1 \leq n , m \leq 10^9)$

第二行两个整数 $x , y$ , 表示有 $x$ 对位于左右边界的点和 $y$ 对位于上下边界的点。 $(1 \leq x \leq min(m + 1 , 10^5) , 1 \leq y \leq min(n + 1,10^5))$

接下来 $x$ 行 , 每行两个整数 $a , b$ 分别表示位于左边界和右边界的点的纵坐标。 $(0 \leq a , b \leq m)$

接下来 $y$ 行 , 每行两个整数 $c , d$ 分别表示位于下边界和上边界的点的横坐标。 $(0 \leq c , d \leq n)$

输出格式

输出一行一个整数 , 表示最大的划分块数。

样例输入

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

样例输出

13

样例解释

按照上图的划分方式可以得到最多的块数 , 13块。