시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 163 29 17 20.732%

문제

견우와 직녀는 여러 개의 섬과 절벽으로 이루어진 장소에 살고 있다. 따라서 평상시에는 절벽을 건너지 못 하기 때문에 서로 만날 수가 없다.

하지만 7월 7일은 특별한 날이다. 이 날에는 까마귀와 까치가 서로 힘을 합쳐 다리를 만들어, 견우와 직녀가 절벽에 상관없이 서로 만날 수 있기 때문이다.

최근에 까마귀와 까치에게 문제가 생겼다. 급속도로 진행된 고령화로 인해서 견우와 직녀가 한 번에 만날 수 있을 만큼 커다란 오작교를 만들 수 없는 상태이다. 요즘에는 견우와 직녀가 만날 수 있도록 최소한의 절벽에만 다리를 만들어 주고 있었다.까마귀와 까치는 이마저도 힘들었기 때문에, 1분간 오작교를 만들면 몇 분 동안은 꼭 쉬는 시간을 가져야 했다. 

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

T = 3 T = 4

위의 그림의 경우에 초록색이 오작교를 건널 수 있는 시간이고, 흰색은 오작교를 건널 수 없는 시간이다.

주기가 3인 경우, 처음에 0분일 때 오작교를 건널 수 있다. 그리고 1분과 2분에는 까마귀와 까치가 휴식을 취하기 때문에 건널 수 없다. 그리고 3분 뒤인 3분에 오작교를 건널 수 있다. 또 다시 4분과 5분에 까마귀와 까치는 쉬는 시간을 가진다. 다시 3분 뒤인 6분이 되면, 견우는 오작교를 건널 수 있다.

주기가 4인 경우, 처음에 0분일 때 오작교를 건널 수 있다. 그리고 1분과 2분, 3분 까지는 까마귀와 까치가 휴식을 취하기 때문에 건널 수 없다. 그리고 4분 뒤인 4분에 오작교를 건널 수 있다. 또 다시 5분과 6분, 7분에 까마귀와 까치는 쉬는 시간을 가진다. 다시 4분 뒤인 8분이 되면 견우는 오작교를 건널 수 있다.

만약, 오작교를 한 번 건넌 뒤에 또 다시 오작교로 이동하면, 견우가 더 이상 이동할 수 없는 순간이 올 수도 있다.

이렇게 되면, 까치와 까마귀에게 굉장히 미안하면서도 민망해지기 때문에 견우는 오작교를 두 번 연속으로 건너는 일은 피하려고 한다.

이런 상황에서도 까마귀와 까치는 견우와 직녀를 도와주고 싶었기 때문에, 견우가 원하는 다리에서 주기가 M 분인 다리를 하나 더 놓아주겠다고 한다. 다만, 아래와 같이 절벽이 가로와 세로로 교차하는 경우에는 까마귀와 까치가 다리를 만들어 줄 수 없다고 한다.

아래 지형정보에서 검은색은 절벽을 의미하고, 흰색은 오작교를 의미하며 파란색은 견우가 건널 수 있는 일반적인 땅을 의미한다.

견우는 짧은 만남이 이런 악조건에서 더욱 짧아지는 것을 원하지 않았다. 그리고 마침내, 견우는 직녀를 가장 빠르게 만나기 위해 오작교를 설치해야 하는 장소를 찾았다. 이때, 견우가 직녀에게 도착할 수 있는 최소의 시간을 찾아라.

입력

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

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

또한, 각 칸에 들어가는 정수의 의미는 다음과 같다.

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

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

이 문제에서 견우와 직녀가 무조건 만날 수 있는 경우만 주어진다.

출력

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

예제 입력 1

5 5
1 1 1 1 1
0 6 0 0 0
1 1 0 1 1
1 1 0 1 1
1 1 0 1 1

예제 출력 1

8

파란색으로 칠해진 지역이 견우가 이동할 수 있는 평범한 땅이고,

검은색으로 칠해진 부분을 절벽, 흰색 바탕에 정수가 쓰여 있는 지역을 쓰여 있는 수만큼 주기를 가지는 오작교라고 하자.

또한, 지형의 좌표는 왼쪽 위부터 (0, 0)으로 시작한다.

위 그림에서 (4, 2)에 주기가 5분인 오작교를 놓아보자.

1분에 (0, 1)위치에 견우가 도착하고, 오작교의 주기가 6분이기 때문에 4분 대기 후 6분에 다리를 건널 수 있다.

7분에 다리를 지나 (2, 1)에 견우가 위치하고, 9분에 (4, 1)위치에 도착한다.

오작교의 주기가 5분이기 때문에 견우는 대기시간 없이 10분에 바로 오작교를 건넌 후에 (4, 4)에 12분에 도착한다.

단, 오작교를 (1, 4)위치에 놓는다면, 대기시간 없이 8분 만에 직녀가 있는 위치까지 올 수 있다.

그리고, 해당 경우가 바로 견우가 직녀에게 도착할 수 있는 최단 시간이다.

출처