Rectangular Pizza

Interview

Time limit1sMemory limit1024 MB

Summary

Given the cut positions on a W by H pizza, count the slices whose area is at most K.

Level: Medium5 of 10
Topics: Sorting, Two pointers, Binary search
Solved: No attempts yet

Problem

Yongmo is in charge of preparing pizza for club members to share at the CTP event.

The pizza Yongmo ordered is a rectangle with width $W$ and height $H$ . In both the horizontal and vertical directions, there is at least one straight cut across the pizza. Each cut is at a natural number distance of 1 or more from the bottom edge or the left edge.

When the pizza has $W$ = 7 and $H$ = 5, with a horizontal cut at $y$ = 2 and vertical cuts at $x$ = 1 and $x$ = 5, the slices have the sizes shown in the figure above.

The CTP staff cannot give a slice to a member if its size is greater than $K$ , because one person would find it hard to eat. The staff counts the slices that can be given to members. Given the pizza information, find how many slices the CTP staff can give to members.

Input

The first line contains $W$ , $H$ , and $K$ separated by spaces. $K$ is the maximum size of a slice that a member can eat.

The second line contains $N$ , the number of horizontal cuts.

The third line contains the vertical positions of the horizontal cuts $y_1, y_2, \cdots, y_N$ separated by spaces.

The fourth line contains $M$ , the number of vertical cuts.

The fifth line contains the horizontal positions of the vertical cuts $x_1, x_2, \cdots, x_M$ separated by spaces.

Output

Print the number of pizza slices that the CTP staff can give to members.

Constraints

$2 \le W, H \le 10^9$
$1 \le K \le W \times H$
$1 \le N \le \min(H - 1, 100\,000)$ , $1 \le M \le \min(W - 1, 100\,000)$
$1 \le x_i \le W - 1$ , $1 \le y_i \le H - 1$ , and $x_i$ and $y_i$ are natural numbers.
The sequences $x_1, x_2, \cdots, x_M$ and $y_1, y_2, \cdots, y_N$ are in ascending order.

Examples2

Example 1
Input
```
7 5 6
1
2
2
1 5
```
Expected output
```
4
```
Example 2
Input
```
4 4 3
1
2
1
2
```
Expected output
```
0
```