28081번 - 직사각형 피자

문제

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

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

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

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

입력

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

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

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

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

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

출력

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

제한

• 2ドル ≤ W, H ≤ 10^9$
• 1ドル ≤ K ≤ W \times H$
• 1ドル ≤ N ≤ \min(H - 1, 100,000円),ドル 1ドル ≤ M ≤ \min(W - 1, 100,000円)$
• 1ドル ≤ x_i ≤ W - 1,ドル 1ドル ≤ y_i ≤ H - 1,ドル $x_i$와 $y_i$는 자연수이다.
• $x_1, x_2, \cdots, x_M$과 $y_1, y_2, \cdots, y_N$은 오름차순인 수열이다.

힌트