교육방송 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인 경우

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

피곤한 귀가길 timer 1s memory 256MB

피곤한 귀가길 1s 256MB