2023-open-t3_Garden — JOI JOI_open
Task type: batch | Time limit: 2 s | Memory limit: 1024 MB | Difficulty: 21
Algorithms: line sweep, data structures, modular arithmetic, optimization

![](_page_0_Picture_0.jpeg)

The 22nd Japanese Olympiad in Informatics (JOI 2022/2023)
JOI Open Contest
August 5, 2023
garden

### Garden

JOI Kingdom is a mysterious kingdom which has a boundless expanse of territory. JOI-kun, the king of JOI Kingdom, is planning to cut a part of the territory and make his garden.

The territory of JOI Kingdom is considered as a sufficiently large 2-dimensional grid. The grid is paved with square cells from the top to the bottom and from the left to the right. There is a cell, which is the origin of the coordinates. Let $(x, y)$ denote the cell one arrives at when one moves from the origin to the right direction for the distance of $x$ cells and to the upward direction for the distance of $y$ cells. Here, the left direction for the distance of $a$ cells means the right direction for the distance of $-a$ cells. Similarly, the downward direction for the distance of $a$ cells means the upward direction for the distance of $-a$ cells.

Some artworks are placed on the territory. The artworks are classified into two types, Type A and Type B, according to the way to be placed in the territory.

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

Note that a cell may contain several artworks of different kinds.

JOI-kun is planning to choose a rectangular region on the grid to make a garden. In other words, he will choose 4 integers $a$, $b$, $c$, $d$. Then the cells of the form $(x, y)$, where $x$, $y$ are integers satisfying $a \le x \le b$, $c \le y \le d$, will constitute JOI-kun's garden. Since JOI-kun likes to see artworks of many kinds, for any of the $N + M$ kinds of artworks, JOI-kun's garden should contain at least one artwork of that kind. On the other hand, the citizens of JOI Kingdom will be angry if JOI-kun plans to make a too large garden. Therefore, JOI-kun wants to minimize the number of cells in the garden so that the above condition is satisfied.

Write a program which, given information of artworks, calculates the minimum number of cells in JOI-kun's garden.

### Input

Read the following data from the standard input.

```
N M D
P1 Q1
P2 Q2
...
PN QN
R1 S1
R2 S2
...
RM SM
```

### Output

Write one line to the standard output. The output should contain the minimum number of cells in JOI-kun's garden.

### Constraints

- $N \ge 1$.
- $M \ge 1$.
- $N + M \le 500\,000$.
- $1 \le D \le 5\,000$.
- $0 \le P_i < D$ ($1 \le i \le N$).
- $0 \le Q_i < D$ ($1 \le i \le N$).
- $0 \le R_j < D$ ($1 \le j \le M$).
- $0 \le S_j < D$ ($1 \le j \le M$).
- Given values are all integers.

### Subtasks

1. (15 point) $M \le 8$.
2. (6 points) $D \le 10$, $N + M \le 5000$.
3. (8 points) $D \le 50$, $N + M \le 5000$.
4. (16 points) $D \le 100$, $N + M \le 5000$.
5. (30 points) $N + M \le 5000$.
6. (25 points) No additional constraints.

### Sample Input and Output

| Sample Input 1 | Sample Output 1 |
|---|---|
| `2 1 5` <br> `1 4` <br> `2 2` <br> `0 0` | `8` |

The following figure describes the cells $(x, y)$, where $x, y$ are integers satisfying $0 \le x < 10$, $0 \le y < 10$, in the territory of JOI Kingdom.

![](_page_2_Figure_13.jpeg)

In this figure, circles and diamond shapes are artworks of type $A$ and $B$, respectively. An integer in a circle or a diamond shape describes the kind of the artwork. If JOI-kun chooses $a = 1$, $b = 2$, $c = 2$, $d = 5$, JOI-kun's garden is a black rectangular region. In this case, JOI-kun's garden has at least one artwork of any of the 3 kinds of artworks. The number of cells in the garden is 8. Since there is no garden which satisfies the condition and which has smaller number of cells, output 8.

This sample input satisfies the constraints of all the subtasks.

| Sample Input 2 | Sample Output 2 |
|---|---|
| `3 4 100` <br> `20 26` <br> `81 56` <br> `20 3` <br> `58 71` <br> `74 82` <br> `95 61` <br> `95 61` | `2840` |

This sample input satisfies the constraints of Subtasks 1, 4, 5, 6.

| Sample Input 3 | Sample Output 3 |
|---|---|
| `5 7 5000` <br> `1046 365` <br> `4122 1166` <br> `4009 2896` <br> `1815 4065` <br> `4372 1651` <br> `2382 123` <br> `1475 836` <br> `3313 4005` <br> `2579 568` <br> `4300 4867` <br> `1050 3214` <br> `3589 4653` | `10543092` |

This sample input satisfies the constraints of Subtasks 1, 5, 6.

Starter code: