Problem Description

JOI Kingdom is a mysterious kingdom with an endless expanse of territory. JOI is the king of JOI Kingdom, and he is planning to partition a part of the territory to build his garden.

The JOI network can be considered as a sufficiently large two-dimensional grid, composed of square cells densely tiled from top to bottom and from left to right. There is a cell that serves as the coordinate origin. Let $(x, y)$ denote the cell reached by moving $x$ cells to the right from the origin and then $y$ cells upwards. Here, moving $a$ cells to the left means moving $-a$ cells to the right. Similarly, moving $a$ cells downwards means moving $-a$ cells upwards.

Within the territory, there are some artworks. These artworks are classified into Type A and Type B based on how they are placed on the territory.

• There are $N$ types of Type A artworks. The $i$-th type of artwork ($1 \le i \le N$) is placed on each cell of the form $(P_i + kD, Q_i + lD)$, where $k, l$ are integers.
• There are $M$ types of Type B artworks. The $j$-th type of artwork ($1 \le j \le M$) is placed on each cell of the form $(R_j + kD, y)$ (where $k, y$ are integers) or $(x, S_j + lD)$ (where $l, x$ are integers).

Note that a cell may contain multiple artworks of different types.

JOI plans to select a rectangular area in the grid to build his garden. In other words, he will choose four integers $a, b, c, d$. Then, cells of the form $(x, y)$ will constitute JOI's garden, where $x, y$ are integers satisfying $a \le x \le b, c \le y \le d$. Since JOI enjoys seeing various artworks, for any of the $N + M$ types of artworks, at least one of them must be included in JOI's garden. On the other hand, if the garden JOI plans to build is too large, the residents of JOI Kingdom will be angry. Therefore, JOI wants to minimize the number of cells in the garden while satisfying the above conditions.

Given the information about the artworks, write a program to calculate the minimum number of cells in JOI's garden.

Input Format

The first line contains three integers $N, M, D$.

The next $N$ lines each contain two integers $P_i, Q_i$.

The next $M$ lines each contain two integers $R_j, S_j$.

Output Format

Output a single integer, which is the minimum number of cells in JOI's garden.

Sample Input and Output

Sample Input #1

2 1 5
1 4
2 2
0 0

Sample Output #1

8

Sample Input #2

3 4 100
20 26
81 56
20 3
58 71
74 82
95 61
95 61

Sample Output #2

2840

Sample Input #3

5 7 5000
1046 365
4122 1166
4009 2896
1815 4065
4372 1651
2382 123
1475 836
3313 4005
2579 568
4300 4867
1050 3214
3589 4653

Sample Output #3

10543092

Notes/Hints

[Sample Explanation #1]

The following diagram shows the cells in JOI Kingdom that satisfy $0 \le x < 10, 0 \le y < 10$.

In this diagram, circles and diamonds represent Type A and Type B artworks, respectively. The integers inside the circles or diamonds indicate the types of artworks. If JOI chooses $a = 1, b = 2, c = 2, d = 5$, JOI's garden will be the black rectangular area. In this case, for each of the three types of artworks, at least one of each type will be included in JOI's garden. The number of cells in the garden is $8$. Since there is no smaller garden that satisfies the conditions, the output is $8$.

This sample satisfies the constraints of all subtasks.

[Sample Explanation #2]

This sample satisfies the constraints of subtasks $1, 4, 5, 6$.

[Sample Explanation #3]

This sample satisfies the constraints of subtasks $1, 5, 6$.

[Data Range]

For all data, the following constraints are satisfied:

• $N, M \ge 1$
• $N + M \le 5 \times 10^5$
• $1 \le D \le 5,000$
• $0 \le P_i, Q_i, R_j, S_j < D$

Detailed subtask additional constraints and scores are as follows:

见题面 Input 部分

见题面 Output 部分