Alpha Supercomputer (Alpha-S) is composed of a wired network of N computers. The computers are placed in an L x W grid that contains obstacles and walls. The efficiency of Alpha-S increases while the total length of the wires decreases. Our aim is to make the most efficient Alpha-S.

We know that it is possible to connect all computers and all computers have to be connected. Wires can only be installed as horizontal or vertical line segments. A wire can connect exactly two computers. A computer can have more than one cable. Each wire segment starts at the center of a cell and ends at the center of another cell. The distance between two neighbor cell centers is 1 unit. Here’s an example that illustrates the most efficient connection for Alpha-S:

Constraints:

• Number of computers; 1 <= N <= 100
• The grid; 1 <= L,W <= 200

Input format:

• The first line is composed of three integers L, W and N.
• Each of the next N lines has two integers x and y (0 <= x < L, 0 <= y < W); the position of a computer.
• Line N+2 contains an integer T, the number of obstacles. Thera will be at most one obstacle in a cell in the grid.
• Each of the next T lines has two integers x and y (0 <= x < L, 0 <= y < W); the position of an obstacle.

Output format:

• Output is just one integer; the length of the wires of the most efficient Alpha-S.

(Problem credit: Fatih Gelgi)