오븐을 부수고 달려라, 쿠키!

어느 날 마녀가 과자 공장을 습격해 쿠키를 모두 오븐에 가두었다. 오븐 바닥은 $H \times W$ 격자다. 쿠키는 1초에 상하좌우로 한 칸 움직이거나 그 자리에 그대로 있는다. 쿠키가 한곳에 모이면 마녀가 의심하기 때문에 한 칸에는 쿠키가 하나만 있을 수 있다.

쿠키를 사랑하는 당신은 바닥을 조사해 부실한 칸을 찾아냈다. 다행히 탈출해야 하는 쿠키의 수와 부실한 칸의 수가 정확히 같다. 쿠키가 부실한 칸에 올라서면 그 바닥이 곧바로 무너지고, 쿠키는 구멍으로 빠져나간다. 한 번 무너진 칸은 마녀가 마법으로 막아 버리므로 구멍 하나로 탈출하는 쿠키는 최대 하나다. 막힌 칸은 장애물이라 다른 쿠키가 들어갈 수 없다. 아직 무너지지 않은 부실한 칸도 밟는 순간 탈출이 일어나므로, 부실한 칸을 밟고 지나가는 이동은 없다.

모든 쿠키는 매초 동시에 움직이고, 1초에 최대 한 칸만 움직인다. 이동이 끝난 시점에 한 칸에 쿠키가 둘 이상 있지만 않으면 되고, 이웃한 두 쿠키가 같은 초에 자리를 맞바꿔도 된다. 같은 초에 두 쿠키가 같은 부실한 칸으로 들어갈 수는 없다.

마지막 쿠키까지 모두 탈출하는 데 필요한 최소 시간을 구하자.

위 그림은 첫 번째 예제 입력에서 쿠키가 움직이는 경로다. 회색 칸은 바닥이 부실한 칸이고, 검은색 칸은 이미 무너져 장애물이 생긴 칸이다.

첫째 줄에 격자의 높이 $H$, 너비 $W$, 쿠키와 부실한 칸의 개수 $N$이 주어진다. ($1 \le H$, $1 \le W$, $H \times W \le 100$, $1 \le N \le H \times W / 2$)

다음 $N$개 줄에 쿠키의 위치 $r$과 $c$가 한 줄에 하나씩 주어진다. 그다음 $N$개 줄에 부실한 칸의 위치 $r$과 $c$가 한 줄에 하나씩 주어진다. ($1 \le r \le H$, $1 \le c \le W$) 주어지는 $2N$개의 위치는 모두 서로 다르다.

첫째 줄에 모든 쿠키가 탈출하는 데 걸리는 최소 시간을 초 단위로 출력한다. 모든 쿠키가 탈출하지 못하면 -1을 출력한다.