给定一个左下角位于 (0,0) 右上角位于 (n,m) 的矩形 , 矩形的四条边都与坐标轴平行 , 你需要将它划分成尽可能多的块数。
划分的规则如下:
- 每次会给出两个点 p,q , 你需要在点 p,q 之间连一条线来划分矩形 , 保证 p,q 分别在矩形的一组对边上 , 即要么分别在左右边界上 , 要么分别在上下边界上。
- 连的线并不要求是直线 , 可以是曲线 , 但不能与自己有交点 , 不能与矩形边界有除 p,q 以外的交点。
- 两条线最多有一个交点 , 如果有交点 , 那么一定是在交点处交叉。
- 线的两端在同一组对边上的线互不相交
- 保证给出的所有点两两不同
输出最多可以划分多少块。
输入格式
第一行两个整数 n,m , 含义如题面所示。 (1≤n,m≤109)
第二行两个整数 x,y , 表示有 x 对位于左右边界的点和 y 对位于上下边界的点。 (1≤x≤min(m+1,105),1≤y≤min(n+1,105))
接下来 x 行 , 每行两个整数 a,b 分别表示位于左边界和右边界的点的纵坐标。 (0≤a,b≤m)
接下来 y 行 , 每行两个整数 c,d 分别表示位于下边界和上边界的点的横坐标。 (0≤c,d≤n)
输出格式
输出一行一个整数 , 表示最大的划分块数。
样例输入
3 4
3 2
1 2
2 1
3 3
1 1
2 2
样例输出
13
样例解释
按照上图的划分方式可以得到最多的块数 , 13块。