아이템 먹기

N × M 크기의 격자 지도에 아이템과 장애물이 놓여 있다. 시작점은 왼쪽 아래 칸 (1, 1)이고, 도착점은 오른쪽 위 칸 (N, M)이다.

한 번 이동할 때는 오른쪽이나 위쪽으로만 한 칸 이동할 수 있다. 장애물이 있는 칸은 지나갈 수 없다. 도착점에 도착하기 전까지 지도에 있는 모든 아이템을 먹어야 한다.

이 조건을 만족하는 이동 경로의 개수를 구하라.

첫째 줄에 정수 N, M, A, B가 주어진다. N과 M은 각각 격자의 가로와 세로 크기이며 1 ≤ N, M ≤ 100이다. A는 아이템의 개수이고 A ≥ 1이다. B는 장애물의 개수이고 B ≥ 0이다.

다음 A개의 줄에는 아이템의 위치가 주어진다. 이어지는 B개의 줄에는 장애물의 위치가 주어진다. 각 위치는 두 정수 x, y로 주어지며, 왼쪽 아래 칸이 (1, 1), 오른쪽 위 칸이 (N, M)이다.

조건을 만족하는 이동 경로의 개수를 첫째 줄에 출력한다. 정답은 int 범위 안에 있다.