피곤한 귀가길

교육방송 KOIBS 스타강사 택쌤이 방송 촬영 스케줄을 마치고 집으로 귀가하려고 한다. 택쌤은 너무 피곤하므로, 귀가 길에 되도록이면 아무 일 없이 집에 가고 싶다.

문제는 택쌤이 너무 인기가 많다는 점이다. 너무 인기가 많아서, 현재 밖에 있는 모든 사람들은 그의 얼굴만 봐도 사진을 찍고 싸인을 요구하러 달려올 것이다.

사람들은 2차원 격자점 위에 서있으며, 택쌤의 현위치는 (1,1)이고, 택쌤의 집은 (N,M)이다.

택쌤과 어떤 사람이 맨하탄 거리로 K 이하의 거리로 들어오면, 그 사람은 무조건적으로 반응하여 택쌤에게 뛰어올 것이다.

여기서 두 격자점( x1 , y1 )과 ( x2 , y2 )의 맨하탄 거리는 |x1-x2|+|y1-y2|와 같다.(|x|는 절대값 x를 의미하며, 부호를 뗀 수치를 말한다.)

참고로 택쌤은 아는 길로만 다니므로, 1≤x≤N, 1≤y≤M을 만족하는 (x,y) 격자점으로만 다닌다.

또한 이 지역에 길은 아래 그림과 같이 정수 좌표의 가로선과 세로선으로만 나 있다.

그림 1. 붉은 색(택쌤의 경로)와 푸른 색(사람들), K=2인 경우

택쌤이 사람들의 눈에 띄지 않고 집으로 귀가할 수 있는 가장 짧은 경로의 길이를 출력하는 프로그램을 작성하라.

입력

첫 줄에 격자판의 크기인 N과 M이 공백을 사이에 두고 주어진다.

둘째 줄에 사람들의 수인 P와 사람들의 시야 범위인 K가 공백을 사이에 두고 주어진다.

그 다음 P줄에 걸쳐서, 사람들의 위치를 나타내는 좌표 x_i, y_i가 공백을 사이에 두고 주어진다.

[제약조건]

모든 부분문제에 있어서 1 ≤ N, M ≤ 1\,500, 1 ≤ P ≤ 5\,000, 0 ≤ K ≤ 1\,500, 1 ≤ x_i ≤ N, 1 ≤ y_i ≤ M 을 만족한다. P는 항상 (N*M-2) 이하이다.

모든 부분문제에 있어서 어떤 (x_i,\ y_i)도 (1,\ 1)이나 (N,\ M)이 아니다. 어떤 두 사람도 같은 위치에 있지 않다.

모든 입력 값은 정수이다.

출력

첫 줄에 택쌤이 집으로 귀가할 수 있는 가장 짧은 경로의 길이를 출력한다.

만약 가능한 경로가 없으면 -1를 출력한다. 이는 다음과 같은 경우도 포함한다. (택쌤이 출발하자마자 어떤 사람의 시야에 닿는 경우나, 택쌤의 집에 어떤 사람의 시야가 닿는 경우)

부분문제

예제

태그

출처

JUNGOL - ohjtgood

피곤한 귀가길 1s 256MB