배관공과 사나운 개

당신은 ICPC(International Community for Pipe Connection)의 자랑스러운 배관공이고, 새 작업을 맡았다. 담당 구역은 동서로 $W$칸, 남북으로 $H$칸인 직사각형이다. 서쪽에서 $i$번째, 북쪽에서 $j$번째 칸을 $(i, j)$라고 부른다. 가장 서쪽이면서 가장 북쪽인 칸은 $(1, 1)$이고, 가장 동쪽이면서 가장 남쪽인 칸은 $(W, H)$이다. 경관을 위해 칸 $(i, j)$에는 $i$와 $j$가 모두 홀수일 때, 그리고 그때만 집이 정확히 하나 있다.

당신의 작업은 구역의 모든 집이 물을 공급받도록 수도관망을 건설하는 것이다. 수도관망은 여러 파이프라인으로 이루어진다. 파이프라인은 하나 이상의 관을 이어서 만들며, 관 $l$개로 이루어진 파이프라인은 다음과 같이 건설한다.

1. 첫 번째 집을 고르고, 그 집을 특수관으로 지하 수원과 연결한다.
2. 각 $i$($2 \le i \le l$)에 대해 $i$번째 집을 고르고, 그 집을 일반관으로 $(i-1)$번째 집과 연결한다. 구역이 경사지이므로 다음 집을 고르는 데에는 조건이 있다. $(i-1)$번째 집의 칸을 $(x, y)$라 하면 $i$번째 집은 $(x-2, y+2)$, $(x, y+2)$, $(x+2, y+2)$ 중 하나에 있어야 하고, 두 집을 잇는 일반관은 각각 $(x-1, y+1)$, $(x, y+1)$, $(x+1, y+1)$에 놓인다.

파이프라인을 여러 개 건설할 때는 다음 규칙도 지켜야 한다.

• 각 집을 지나는 파이프라인은 정확히 하나다.
• 한 칸에 관을 여러 개 놓을 수 있다.

일반관은 흔하므로 개수 제한 없이 사용할 수 있다. 특수관은 특별하므로 ICPC 규정에 따라 이 작업에서 사용할 수 있는 개수가 제한된다.

특수관 개수 제한 말고도 작업을 방해하는 요소가 하나 더 있다. 바로 사나운 개다. 집이 없는 칸 중 일부는 사나운 개의 집이다. 각 개는 항상 자기 집 칸에 머무른다. 여러 마리가 한 칸을 집으로 쓰는 일은 없으므로, 각 칸에 사는 개는 많아야 한 마리다.

아래 그림은 $5 \times 5$ 구역에 특수관 4개로 건설한 수도관망의 예이며, 첫 번째 예제에 해당한다.

개가 없는 칸에 일반관을 하나 놓는 데는 1단위 시간이 걸린다. 개가 사는 칸에 일반관을 하나 놓는 데는 사나운 개와 싸워야 하므로 2단위 시간이 걸린다. 한 칸에 관을 여러 개 놓을 때도 관 하나마다 개가 없는 칸이면 1단위, 개가 사는 칸이면 2단위 시간이 든다. 특수관은 아주 특별해서 놓는 데 0단위 시간이 든다.

당신은 이 작업을 최대한 빨리 끝내고 싶다. 다행히 개가 사는 칸의 목록이 있다. 허용된 개수의 특수관만으로 모든 집에 물을 공급하는 수도관망을 건설할 수 있는지 판정하고, 가능하다면 건설에 드는 최소 총 시간을 구하는 프로그램을 작성하시오.

입력은 테스트 케이스 하나로 이루어지며 형식은 다음과 같다.

W H K
N
x1 y1
...
xN yN

모든 수는 정수다. 첫째 줄에 $W$, $H$, $K$가 주어진다. $W$는 동서 방향 칸 수($1 \le W < 10000$), $H$는 남북 방향 칸 수($1 \le H < 10000$)이며, $W$와 $H$는 모두 홀수다. $K$는 이 작업에서 사용할 수 있는 특수관의 개수다($1 \le K \le 100000000$). 둘째 줄에 구역에 있는 개의 수 $N$($0 \le N \le 100000$)이 주어진다. 이어지는 $N$개 줄에는 각각 정수 $x_i$와 $y_i$가 주어지며, $i$번째 개의 집이 칸 $(x_i, y_i)$라는 뜻이다. 이 값들은 다음 조건을 만족한다.

• $1 \le x_i \le W$, $1 \le y_i \le H$.
• $x_i$와 $y_i$ 중 적어도 하나는 짝수다.
• $i \ne j$이면 $(x_i, y_i) \ne (x_j, y_j)$이다. 즉, 같은 칸에 사는 개는 둘 이상 없다.

특수관을 최대 $K$개만 사용해 모든 집에 물을 공급하는 수도관망을 건설할 수 있으면 건설에 드는 최소 총 시간을 출력한다. 불가능하면 -1을 출력한다.