직사각형 피자

아직 제출이 없습니다시간 제한1초메모리 제한1024 MB

문제

용모는 CTP 행사에서 부원들과 나누어 먹을 피자를 준비하는 임무를 맡았다.

용모가 주문한 피자는 가로 길이가 WW, 세로 길이가 HH인 직사각형 모양이며, 가로 방향이나 세로 방향으로 각 방향에 대해 피자를 가르는 직선 커팅이 피자의 아래쪽 끝이나 왼쪽 끝을 기준으로 1 이상의 자연수만큼의 거리에 하나 이상 존재한다.

피자의 크기가 WW = 7, HH = 5이며, 가로 방향으로 yy = 2인 위치에 커팅이 있고 세로 방향으로 xx = 1, xx = 5인 위치에 커팅이 있는 경우 피자의 조각 각각의 크기는 위 그림과 같다.

CTP 운영진에서는 주문한 피자의 조각 하나의 크기가 KK보다 크면 혼자 먹기가 힘들어 부원에게 나누어 줄 수 없기 때문에, 피자 조각들 중에서 부원들에게 나누어 줄 수 있는 피자 조각의 개수를 구해 나누어 주려 한다. 피자의 정보가 주어질 때, CTP 운영진이 부원들에게 나누어 줄 수 있는 피자의 개수를 구해보자.

입력

첫 번째 줄에 피자의 가로 길이 WW와 세로 길이 HH, 부원들이 먹을 수 있는 피자 조각의 최대 크기 KK가 공백으로 구분되어 주어진다.

두 번째 줄에 가로 방향 커팅의 개수 NN이 주어진다.

세 번째 줄에 가로 방향 커팅의 세로 위치 y_1,y_2,,y_Ny\_1, y\_2, \cdots, y\_N이 공백으로 구분되어 주어진다.

네 번째 줄에 세로 방향 커팅의 개수 MM이 주어진다.

다섯 번째 줄에 세로 방향 커팅의 가로 위치 x_1,x_2,,x_Mx\_1, x\_2, \cdots, x\_M이 공백으로 구분되어 주어진다.

출력

CTP 운영진이 부원들에게 나누어 줄 수 있는 피자 조각의 개수를 출력한다.

제한

  • 2W,H1092 ≤ W, H ≤ 10^9
  • 1KW×H1 ≤ K ≤ W \times H
  • 1Nmin(H1,100,000)1 ≤ N ≤ \min(H - 1, 100\\,000), 1Mmin(W1,100,000)1 ≤ M ≤ \min(W - 1, 100\\,000)
  • 1x_iW11 ≤ x\_i ≤ W - 1, 1y_iH11 ≤ y\_i ≤ H - 1, x_ix\_iy_iy\_i는 자연수이다.
  • x_1,x_2,,x_Mx\_1, x\_2, \cdots, x\_My_1,y_2,,y_Ny\_1, y\_2, \cdots, y\_N은 오름차순인 수열이다.