Collecting Items

An N × M grid map contains items and obstacles. The starting cell is the bottom-left cell (1, 1), and the destination is the top-right cell (N, M).

Each move goes exactly one cell to the right or one cell upward. You cannot pass through a cell that contains an obstacle. Before reaching the destination, you must collect every item on the map.

Find the number of movement paths that satisfy these conditions.

The first line contains four integers N, M, A, and B. N and M are the width and height of the grid, respectively, and 1 ≤ N, M ≤ 100. A is the number of items, with A ≥ 1. B is the number of obstacles, with B ≥ 0.

Each of the next A lines contains the position of one item. Each of the following B lines contains the position of one obstacle. Each position is given as two integers x and y; the bottom-left cell is (1, 1), and the top-right cell is (N, M).

Print the number of movement paths that satisfy the conditions on the first line. The answer fits in the range of int.