Vương quốc JOI là một vương quốc bí ẩn có lãnh thổ rộng vô tận. Vua JOI-kun định dành một phần lãnh thổ để làm khu vườn của mình.

Lãnh thổ được xem như một lưới hai chiều đủ lớn gồm các ô vuông, trải theo cả chiều ngang và chiều dọc. Chọn một ô làm gốc tọa độ. Ô \((x,y)\) là ô đến được khi đi từ gốc sang phải \(x\) ô và lên trên \(y\) ô. Đi sang trái \(a\) ô tương ứng với đi sang phải \(-a\) ô; đi xuống dưới \(a\) ô tương ứng với đi lên trên \(-a\) ô.

Trên lãnh thổ có các tác phẩm nghệ thuật, được chia thành hai loại A và B theo cách bố trí:

• Có \(N\) kiểu tác phẩm loại A. Với kiểu thứ \(i\) (\(1 \le i \le N\)), một tác phẩm được đặt ở mỗi ô có dạng \((P_i+kD,Q_i+lD)\), trong đó \(k,l\) là các số nguyên.
• Có \(M\) kiểu tác phẩm loại B. Với kiểu thứ \(j\) (\(1 \le j \le M\)), một tác phẩm được đặt ở mỗi ô có dạng \((R_j+kD,y)\) với \(k,y\) nguyên, hoặc có dạng \((x,S_j+lD)\) với \(l,x\) nguyên.

Một ô có thể chứa nhiều tác phẩm thuộc các kiểu khác nhau.

JOI-kun sẽ chọn một vùng hình chữ nhật trên lưới làm vườn. Cụ thể, ông chọn bốn số nguyên \(a,b,c,d\); khu vườn gồm các ô \((x,y)\) với \(x,y\) nguyên thỏa mãn \(a \le x \le b\), \(c \le y \le d\).

Vì thích ngắm nhiều kiểu tác phẩm, JOI-kun muốn khu vườn chứa ít nhất một tác phẩm của mỗi kiểu trong \(N+M\) kiểu. Tuy nhiên, người dân sẽ tức giận nếu khu vườn quá lớn, nên ông muốn số ô trong vườn nhỏ nhất có thể mà vẫn thỏa mãn điều kiện trên.

Hãy viết chương trình tính số ô nhỏ nhất trong khu vườn của JOI-kun khi biết thông tin về các tác phẩm.

Dữ liệu vào

Đọc từ đầu vào chuẩn theo định dạng:

N M D
P_1 Q_1
P_2 Q_2
...
P_N Q_N
R_1 S_1
R_2 S_2
...
R_M S_M

Dữ liệu ra

Ghi một dòng ra đầu ra chuẩn, chứa số ô nhỏ nhất có thể trong khu vườn của JOI-kun.

Ràng buộc

• \(N \ge 1\).
• \(M \ge 1\).
• \(N+M \le 500000\).
• \(1 \le D \le 5000\).
• \(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\)).
• Tất cả các giá trị đầu vào đều là số nguyên.

Phân nhóm

1. \(15\) điểm: \(M \le 8\).
2. \(6\) điểm: \(D \le 10\); \(N+M \le 5000\).
3. \(8\) điểm: \(D \le 50\); \(N+M \le 5000\).
4. \(16\) điểm: \(D \le 100\); \(N+M \le 5000\).
5. \(30\) điểm: \(N+M \le 5000\).
6. \(25\) điểm: Không có ràng buộc bổ sung.

Ví dụ

2 1 5
1 4
2 2
0 0

8

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

2840

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

10543092

Nguồn

JOI Open Contest 2023 - Garden. Tác giả: Yuto Watanabe. Đơn vị công bố: JCIOI (Ủy ban Nhật Bản về Olympic Tin học Quốc tế). Giấy phép: CC BY-SA 4.0.