D - Investigation of Overlapping Advertisement Areas Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君と青木君は、N \times N マスの掲示板にそれぞれ広告を貼ろうとしています。掲示板の各マスは座標 (r, c)（1 \leq r \leq N, 1 \leq c \leq N）で表されます。ここで r は上から数えた行番号、c は左から数えた列番号です。

高橋君は A 個の長方形の広告を、青木君は B 個の長方形の広告を掲示板に貼る予定です。各広告は、左上のマス (r_1, c_1) と右下のマス (r_2, c_2) で指定される長方形の領域を覆います。すなわち、r_1 \leq r \leq r_2 かつ c_1 \leq c \leq c_2 を満たすすべてのマス (r, c) が覆われます。

掲示板の管理人は、高橋君の広告と青木君の広告が重なって貼られるマスがあると見栄えが悪くなるため、重なりが生じるマスの総数を事前に把握したいと考えています。

高橋君の広告のうち少なくとも 1 つに覆われ、かつ青木君の広告のうち少なくとも 1 つに覆われるマスの数を求めてください。同じマスが複数の広告の組み合わせで重複して覆われていても、1 マスとして 1 回だけ数えます。

制約

  • 1 \leq N \leq 500
  • 1 \leq A \leq 100
  • 1 \leq B \leq 100
  • 高橋君の各広告 i（1 \leq i \leq A）について、1 \leq r_{1,i} \leq r_{2,i} \leq N, 1 \leq c_{1,i} \leq c_{2,i} \leq N
  • 青木君の各広告 j（1 \leq j \leq B）について、1 \leq r_{1,j} \leq r_{2,j} \leq N, 1 \leq c_{1,j} \leq c_{2,j} \leq N
  • 入力はすべて整数である

入力

N A B
r_{1,1} c_{1,1} r_{2,1} c_{2,1}
r_{1,2} c_{1,2} r_{2,2} c_{2,2}
:
r_{1,A} c_{1,A} r_{2,A} c_{2,A}
r'_{1,1} c'_{1,1} r'_{2,1} c'_{2,1}
r'_{1,2} c'_{1,2} r'_{2,2} c'_{2,2}
:
r'_{1,B} c'_{1,B} r'_{2,B} c'_{2,B}
  • 1 行目には、掲示板の一辺のマス数 N、高橋君の広告の数 A、青木君の広告の数 B がスペース区切りで与えられる。
  • 続く A 行では、高橋君の広告が 1 行に 1 つずつ与えられる。
  • i 番目の広告（1 \leq i \leq A）は、左上のマス (r_{1,i}, c_{1,i}) と右下のマス (r_{2,i}, c_{2,i}) の 4 つの整数がスペース区切りで与えられる。
  • 続く B 行では、青木君の広告が 1 行に 1 つずつ与えられる。
  • j 番目の広告（1 \leq j \leq B）は、左上のマス (r'_{1,j}, c'_{1,j}) と右下のマス (r'_{2,j}, c'_{2,j}) の 4 つの整数がスペース区切りで与えられる。

出力

高橋君の広告と青木君の広告が重なっているマスの数を 1 行で出力してください。

入力例 1

5 1 1
1 1 3 3
2 2 4 4

出力例 1

4

入力例 2

10 2 2
1 1 5 5
3 7 6 10
4 3 8 6
2 8 5 10

出力例 2

15

入力例 3

100 3 2
1 1 50 50
40 60 80 100
70 1 100 40
30 30 60 70
80 10 100 50

出力例 3

1323

Score : 400 pts

Problem Statement

Takahashi and Aoki are each planning to post advertisements on an N \times N grid bulletin board. Each cell of the bulletin board is represented by coordinates (r, c) (1 \leq r \leq N, 1 \leq c \leq N), where r is the row number counted from the top and c is the column number counted from the left.

Takahashi plans to post A rectangular advertisements, and Aoki plans to post B rectangular advertisements on the bulletin board. Each advertisement covers a rectangular region specified by its top-left cell (r_1, c_1) and bottom-right cell (r_2, c_2). That is, all cells (r, c) satisfying r_1 \leq r \leq r_2 and c_1 \leq c \leq c_2 are covered.

The bulletin board manager is concerned that cells covered by both Takahashi's and Aoki's advertisements will look unsightly, and wants to know the total number of such overlapping cells in advance.

Find the number of cells that are covered by at least one of Takahashi's advertisements and also covered by at least one of Aoki's advertisements. Even if the same cell is covered by multiple combinations of advertisements, it is counted only once.

Constraints

  • 1 \leq N \leq 500
  • 1 \leq A \leq 100
  • 1 \leq B \leq 100
  • For each of Takahashi's advertisements i (1 \leq i \leq A): 1 \leq r_{1,i} \leq r_{2,i} \leq N, 1 \leq c_{1,i} \leq c_{2,i} \leq N
  • For each of Aoki's advertisements j (1 \leq j \leq B): 1 \leq r_{1,j} \leq r_{2,j} \leq N, 1 \leq c_{1,j} \leq c_{2,j} \leq N
  • All input values are integers

Input

N A B
r_{1,1} c_{1,1} r_{2,1} c_{2,1}
r_{1,2} c_{1,2} r_{2,2} c_{2,2}
:
r_{1,A} c_{1,A} r_{2,A} c_{2,A}
r'_{1,1} c'_{1,1} r'_{2,1} c'_{2,1}
r'_{1,2} c'_{1,2} r'_{2,2} c'_{2,2}
:
r'_{1,B} c'_{1,B} r'_{2,B} c'_{2,B}
  • The first line contains the board size N, the number of Takahashi's advertisements A, and the number of Aoki's advertisements B, separated by spaces.
  • The following A lines each describe one of Takahashi's advertisements.
  • The i-th advertisement (1 \leq i \leq A) is given as four space-separated integers representing the top-left cell (r_{1,i}, c_{1,i}) and the bottom-right cell (r_{2,i}, c_{2,i}).
  • The following B lines each describe one of Aoki's advertisements.
  • The j-th advertisement (1 \leq j \leq B) is given as four space-separated integers representing the top-left cell (r'_{1,j}, c'_{1,j}) and the bottom-right cell (r'_{2,j}, c'_{2,j}).

Output

Output the number of cells where Takahashi's advertisements and Aoki's advertisements overlap, on a single line.

Sample Input 1

5 1 1
1 1 3 3
2 2 4 4

Sample Output 1

4

Sample Input 2

10 2 2
1 1 5 5
3 7 6 10
4 3 8 6
2 8 5 10

Sample Output 2

15

Sample Input 3

100 3 2
1 1 50 50
40 60 80 100
70 1 100 40
30 30 60 70
80 10 100 50

Sample Output 3

1323