가장 매운 치즈 조각

직사각형을 가로지르는 두 종류의 서로 교차하지 않는 절단선이 주어질 때, 가장 많은 고추를 담은 조각의 고추 수를 구한다.

보통7기하정렬누적 합아직 제출이 없습니다시간 제한1초메모리 제한512 MB

문제

미르코에게 너비가 SS이고 높이가 VV인 이차원 치즈가 있다. 미르코는 이 치즈에 왼쪽 변과 오른쪽 변을 모두 가로지르는 A형 칼집을 AA개 낸다. 그다음 위쪽 변과 아래쪽 변을 모두 가로지르는 B형 칼집을 BB개 낸다. 같은 종류의 칼집끼리는 서로 만나지 않는다. 치즈 안에는 매운 고추 NN개가 박혀 있고, 각 고추의 위치는 xx, yy 좌표로 주어진다. 치즈를 다 자른 뒤 미르코는 가장 매운 조각, 곧 고추가 가장 많이 들어 있는 조각에 고추가 몇 개인지 알고 싶다. 미르코를 도와주자.

입력

첫째 줄에 치즈의 너비 SS와 높이 VV가 주어진다 (1S1071 \le S \le 10^7, 1V1071 \le V \le 10^7).

둘째 줄에 고추의 개수 NN이 주어진다 (1N1000001 \le N \le 100\,000). 이어지는 NN개 줄에는 고추 하나의 좌표를 나타내는 두 정수 xxyy가 주어진다 (0<x<S0 < x < S, 0<y<V0 < y < V). 어떤 고추도 칼집 위에 놓이지 않으며, 두 고추가 같은 좌표에 있지도 않다.

그다음 줄에는 왼쪽 변과 오른쪽 변을 모두 가로지르는 칼집의 수 AA가 주어진다 (1A1000001 \le A \le 100\,000). 이어지는 AA개 줄에는 두 정수 yLy_LyRy_R이 주어진다. 각각 칼집이 왼쪽 변, 오른쪽 변과 만나는 지점의 yy좌표이다 (0<yL<V0 < y_L < V, 0<yR<V0 < y_R < V).

그다음 줄에는 위쪽 변과 아래쪽 변을 모두 가로지르는 칼집의 수 BB가 주어진다 (1B1000001 \le B \le 100\,000). 이어지는 BB개 줄에는 두 정수 xTx_TxBx_B가 주어진다. 각각 칼집이 위쪽 변, 아래쪽 변과 만나는 지점의 xx좌표이다 (0<xT<S0 < x_T < S, 0<xB<S0 < x_B < S).

왼쪽 변과 오른쪽 변을 가로지르는 칼집끼리는 서로 만나지도, 닿지도 않는다. 위쪽 변과 아래쪽 변을 가로지르는 칼집끼리도 마찬가지다.

좌표는 표준 데카르트 좌표계를 따른다. xx는 왼쪽에서 오른쪽으로 갈수록 커지고, yy는 아래에서 위로 갈수록 커진다.

출력

고추가 가장 많이 들어 있는 조각의 고추 개수를 한 줄에 출력한다.