견우와 직녀

견우와 직녀는 여러 섬과 절벽으로 이루어진 지역에 살고 있다. 이 지역은 격자로 나타낼 수 있고, 상하좌우로 인접한 칸으로 이동하는 데 1분이 걸린다.

7월 7일은 견우와 직녀가 오작교를 건너 만날 수 있는 날이다. 그런데 고령화 때문에 까마귀와 까치가 예전처럼 커다란 오작교를 만들 수 없다. 그래서 요즘에는 일부 절벽에만 다리를 놓아 주고, 그것도 힘들어서 몇 분 주기로 오작교를 짓고 해체하는 작업을 반복한다. 한 번 지은 오작교는 1분 동안 유지된다.

예를 들어 오작교의 주기가 3분과 4분이라면 건널 수 있는 시간은 아래 그림에서 초록색으로 표시한 부분과 같다.

T = 3	T = 4

오작교는 이처럼 매우 불안정하므로 견우는 안전을 위해 두 번 연속으로 오작교를 건너지 않기로 했다.

까마귀와 까치가 견우를 조금이라도 더 도와주려고, 절벽을 정확히 하나 골라 주기가 M분인 오작교를 하나 더 놓아 주기로 했다. 단, 이미 오작교를 지을 예정인 절벽에는 오작교를 하나 더 놓을 수 없고, 아래와 같이 절벽이 가로와 세로로 교차하는 곳에도 오작교를 놓을 수 없다.

아래 그림에서 파란색은 견우가 건널 수 있는 일반적인 땅, 검은색은 절벽, 흰색은 절벽이 교차해서 오작교를 놓을 수 없는 위치를 나타낸다.

견우가 직녀에게 도착할 수 있는 최소 시간을 구해 보자.

첫째 줄에 지형의 행과 열 크기를 나타내는 정수 N (2 ≤ N ≤ 10)과 새로 만들어지는 오작교의 주기를 나타내는 정수 M (2 ≤ M ≤ 20)이 주어진다.

다음 N개의 줄에는 배열의 각 행을 나타내는 N개의 정수가 한 칸씩 빈칸을 사이에 두고 주어진다. 각 칸의 값은 0 이상 20 이하이다.

각 칸의 값은 다음을 뜻한다.

• 1: 이동할 수 있는 일반적인 땅
• 0: 건널 수 없는 절벽
• 2 이상의 수: 적혀 있는 수만큼의 주기를 가지는 오작교

견우의 시작점은 지형의 맨 왼쪽 위 (0, 0)이고, 직녀가 사는 곳은 지형의 맨 오른쪽 아래 (N-1, N-1)이다. 견우가 시작점에서 출발하는 시간은 0분이다. 견우와 직녀가 사는 곳은 일반적인 땅이다.

견우와 직녀가 무조건 만날 수 있는 경우만 주어진다. 주어지는 지형 정보에서 오작교를 반드시 하나 이상 놓을 수 있다. 절벽이 가로와 세로로 교차하는 지점에는 오작교가 설치되어 있지 않다.

견우가 직녀에게 갈 수 있는 최소 시간을 출력한다.