Moving a Unit

In a grid-based game, a unit sometimes has to move from one position to another. Treat the map as an N by M grid, and treat the unit as an A by B rectangle. The unit's position is represented by the top-left cell of that rectangle. The following picture shows one map of size 5 by 5 and one unit of size 2 by 2. S is the starting position and E is the destination.

The unit can move one cell at a time in one of four directions: up, down, left, or right. A move is not allowed if any part of the unit would cover an obstacle cell. In the picture above, moving up from the starting position is not allowed for that reason. A move is also not allowed if any part of the unit would leave the map.

Given the map information and the unit information, find the minimum number of moves needed to move the unit from the starting position to the destination.

The first line contains five integers N, M, A, B, and K: 1 <= N, M <= 500, 1 <= A, B <= 10, and 0 <= K <= 100,000.

Each of the next K lines contains the row and column of one obstacle cell. Rows and columns are numbered from 1 starting at the top-left corner.

The next two lines contain the starting position and the destination position, in that order. Each position is given as the row and column of the unit's top-left cell. The starting position and destination position are different.

The starting position cell itself does not contain an obstacle, and the given top-left positions are within the map.

Print the minimum number of moves. If the unit cannot reach the destination, print -1.