2194번 - 유닛 이동시키기

스타크래프트와 같은 게임을 하다 보면 어떤 유닛을 목적지까지 이동시켜야 하는 경우가 종종 발생한다. 편의상 맵을 N×M 크기의 2차원 행렬로 생각하자. 또한 각각의 유닛은 크기를 가질 수 있는데, 이를 A×B 크기의 2차원 행렬로 생각하자. 아래는 5×5 크기의 맵과 2×2 크기의 유닛에 대한 한 예이다. S는 시작점을 나타내며 E는 끝점을 나타낸다.

유닛은 상하좌우의 네 방향으로만 움직일 수 있다. 단, 유닛의 일부분이 장애물이 설치된 부분(위의 예에서 색이 칠해진 부분)을 지날 경우, 위의 예에서는 시작 위치에서 위로 이동하는 경우는 허용되지 않는다. 위의 예는 유닛을 오른쪽으로 세 칸, 위쪽으로 세 칸 움직이면 목적지에 도달할 수 있고, 이 경우가 가장 적은 이동 회수를 거치는 경우이다. 이동하는 도중에 유닛이 맵 밖으로 나가는 경우는 허용되지 않는다.

맵의 정보와 유닛의 정보가 주어졌을 때, 유닛을 목적지까지 움직이기 위해 필요한 최소의 이동 회수를 구하는 프로그램을 작성하시오.

첫째 줄에 다섯 개의 정수 N, M(1 ≤ N, M ≤ 500), A, B(1 ≤ A, B ≤ 10), K(0 ≤ K ≤ 100,000)가 주어진다. 다음 K개의 줄에는 장애물이 설치된 위치(행 번호, 열 번호)가 주어진다. 그 다음 줄에는 시작점의 위치와 도착점의 위치가 주어진다. 시작점의 위치와 도착점의 위치는 제일 왼쪽 제일 위의 한 점만 주어진다. 시작점의 위치와 도착점의 위치는 같지 않다.

유닛의 시작점에는 장애물이 존재하지 않으며, 시작점과 도착점이 행렬의 범위를 벗어나는 경우는 없다.

첫째 줄에 답을 출력한다. 이동이 불가능한 경우에는 -1을 출력한다.