Rectangle Partition

Problem Description

You are given a rectangle whose bottom-left corner is at $(0, 0)$ and top-right corner is at $(n, m)$; all four sides are parallel to the axes. You need to partition it into as many pieces as possible.

The partition rules are as follows:

1. Each time two points $p, q$ are given, and you must draw a line between $p$ and $q$ to partition the rectangle. It is guaranteed that $p$ and $q$ lie on a pair of opposite sides — either both on the left/right boundaries, or both on the top/bottom boundaries.
2. The line does not have to be straight; it may be curved, but it must not intersect itself, and must not intersect the rectangle boundary at any point other than $p, q$.
3. Two lines have at most one intersection, and if they intersect, they cross at that point.
4. Lines whose endpoints lie on the same pair of opposite sides do not intersect each other.
5. It is guaranteed that all given points are pairwise distinct.

Output the maximum number of pieces into which the rectangle can be partitioned.

Input Format

The first line contains two integers $n, m$, as described ($1 \le n, m \le 10^9$).

The second line contains two integers $x, y$, meaning there are $x$ pairs of points on the left/right boundaries and $y$ pairs of points on the bottom/top boundaries ($1 \le x \le \min(m+1, 10^5)$, $1 \le y \le \min(n+1, 10^5)$).

The next $x$ lines each contain two integers $a, b$, the vertical coordinates of the points on the left and right boundaries respectively ($0 \le a, b \le m$).

The next $y$ lines each contain two integers $c, d$, the horizontal coordinates of the points on the bottom and top boundaries respectively ($0 \le c, d \le n$).

Output Format

Output one integer on a single line: the maximum number of pieces.

Sample Input

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

Sample Output

13

Sample Explanation

According to the partition shown above, the maximum number of pieces is $13$.