D - A Piece of Cake Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

xy -平面上にいくつかのイチゴが載った長方形のケーキがあります。 ケーキは、長方形領域 \lbrace (x, y) : 0 \leq x \leq W, 0 \leq y \leq H \rbrace をちょうど占めます。

ケーキには N 個のイチゴが載っており、i = 1, 2, \ldots, N について、i 番目のイチゴの座標は (p_i, q_i) です。 2 個以上のイチゴが同一の座標にあることはありません。

高橋君は、このケーキを包丁で下記の通りにいくつかのピースに切り分けます。

  • まず、ケーキを通る y 軸に並行な A 本の異なる直線、直線 x = a_1 、直線 x = a_2 、\ldots 、直線 x = a_A のそれぞれにそってケーキを切る。
  • 次に、ケーキを通る x 軸に並行な B 本の異なる直線、直線 y = b_1 、直線 y = b_2 、\ldots 、直線 y = b_B のそれぞれにそってケーキを切る。

その結果、ケーキは (A+1)(B+1) 個の長方形のピースに分割されます。 高橋君はそれらのうちのいずれか 1 個だけを選んで食べます。 高橋君が選んだピースに載っているイチゴの個数としてあり得る最小値と最大値をそれぞれ出力してください。

ここで、最終的にピースの縁となる位置にはイチゴが存在しないことが保証されます。 より形式的な説明は下記の制約を参照してください。

制約

  • 3 \leq W, H \leq 10^9
  • 1 \leq N \leq 2 \times 10^5
  • 0 \lt p_i \lt W
  • 0 \lt q_i \lt H
  • i \neq j \implies (p_i, q_i) \neq (p_j, q_j)
  • 1 \leq A, B \leq 2 \times 10^5
  • 0 \lt a_1 \lt a_2 \lt \cdots \lt a_A \lt W
  • 0 \lt b_1 \lt b_2 \lt \cdots \lt b_B \lt H
  • p_i \not \in \lbrace a_1, a_2, \ldots, a_A \rbrace
  • q_i \not \in \lbrace b_1, b_2, \ldots, b_B \rbrace
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

W H
N
p_1 q_1
p_2 q_2
\vdots
p_N q_N
A
a_1 a_2 \ldots a_A
B
b_1 b_2 \ldots b_B

出力

高橋君が選んだピースに載っているイチゴの個数としてあり得る最小値 m と最大値 M をそれぞれ、下記の形式の通り空白区切りで出力せよ。

m M

入力例 1

7 6
5
6 1
3 1
4 2
1 5
6 2
2
2 5
2
3 4

出力例 1

0 2

全 9 個のピースの内訳は、イチゴが 0 個載ったものが 6 個、イチゴが 1 個載ったものが 1 個、イチゴが 2 個載ったものが 2 個です。 よって、それらのうちのいずれか 1 個だけを選んで食べるとき、選んだピースに載っているイチゴの個数としてあり得る最小値は 0 、最大値は 2 です。

入力例 2

4 4
4
1 1
3 1
3 3
1 3
1
2
1
2

出力例 2

1 1

どのピースにもイチゴが 1 個載っています。

Score : 400 points

Problem Statement

There is a rectangular cake with some strawberries on the xy-plane. The cake occupies the rectangular area \lbrace (x, y) : 0 \leq x \leq W, 0 \leq y \leq H \rbrace.

There are N strawberries on the cake, and the coordinates of the i-th strawberry are (p_i, q_i) for i = 1, 2, \ldots, N. No two strawberries have the same coordinates.

Takahashi will cut the cake into several pieces with a knife, as follows.

  • First, cut the cake along A different lines parallel to the y-axis: lines x = a_1, x = a_2, \ldots, x = a_A.
  • Next, cut the cake along B different lines parallel to the x-axis: lines y = b_1, y = b_2, \ldots, y = b_B.

As a result, the cake will be divided into (A+1)(B+1) rectangular pieces. Takahashi will choose just one of these pieces to eat. Print the minimum and maximum possible numbers of strawberries on the chosen piece.

Here, it is guaranteed that there are no strawberries along the edges of the final pieces. For a more formal description, refer to the constraints below.

Constraints

  • 3 \leq W, H \leq 10^9
  • 1 \leq N \leq 2 \times 10^5
  • 0 \lt p_i \lt W
  • 0 \lt q_i \lt H
  • i \neq j \implies (p_i, q_i) \neq (p_j, q_j)
  • 1 \leq A, B \leq 2 \times 10^5
  • 0 \lt a_1 \lt a_2 \lt \cdots \lt a_A \lt W
  • 0 \lt b_1 \lt b_2 \lt \cdots \lt b_B \lt H
  • p_i \not \in \lbrace a_1, a_2, \ldots, a_A \rbrace
  • q_i \not \in \lbrace b_1, b_2, \ldots, b_B \rbrace
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

W H
N
p_1 q_1
p_2 q_2
\vdots
p_N q_N
A
a_1 a_2 \ldots a_A
B
b_1 b_2 \ldots b_B

Output

Print the minimum possible number of strawberries m and the maximum possible number M on the chosen piece in the following format, separated by a space.

m M

Sample Input 1

7 6
5
6 1
3 1
4 2
1 5
6 2
2
2 5
2
3 4

Sample Output 1

0 2

There are nine pieces in total: six with zero strawberries, one with one strawberry, and two with two strawberries. Therefore, when choosing just one of these pieces to eat, the minimum possible number of strawberries on the chosen piece is 0, and the maximum possible number is 2.

Sample Input 2

4 4
4
1 1
3 1
3 3
1 3
1
2
1
2

Sample Output 2

1 1

Each piece has one strawberry on it.