Module: 지정된 마스크의 모든 하위 패턴을 반복합니다.

Problem

에릭은 대학에서 경비원으로 일하기 때문에 하루 일과를 마치고 건물을 돌아다니며 밤에는 불을 끕니다.
건물은 n층이고 좌우에 2개의 계단이 있습니다. 좌우 계단을 연결하는 복도를 따라 각 층에 m개의 방이 있다. 즉, 건물은 n개의 행과 m + 2개의 열이 있는 직사각형으로 나타낼 수 있습니다. 계단, 중간에 m 기둥 — 객실.

에릭은 지금 1층 왼쪽 계단에 서 있습니다. 그는 모든 곳의 조명을 끄고 싶어하지만, 현재 층의 모든 조명을 끄기 전에 위층으로 올라가고 싶지 않습니다. 물론 불을 끄려면 에릭이 방에 있어야 한다. 에릭은 한 층의 계단을 오르거나 다음 방에서 다음 방/계단 또는 같은 층의 계단으로 1분을 보냅니다. 에릭이 있는 방의 불을 끄는 데 시간이 걸리지 않습니다. 

에릭이 건물의 모든 조명을 끌 수 있는 최소 시간을 찾도록 도와주세요.
Eric은 원래 위치로 돌아갈 필요가 없으며 불이 이미 꺼져 있는 방을 방문할 필요도 없습니다.

입력:
첫 번째 라인은 두 개의 정수 n과 m을 포함합니다 층수와 각 층의 객실 수.
다음 n 줄에는 건물에 대한 설명이 포함됩니다. 각 줄에는 한 층(왼쪽 계단, m방, 오른쪽 계단)을 나타내는 길이 m 2인 0과 1의 문자열이 포함됩니다. 여기서 0은 조명이 꺼져 있음을 의미하고 1은 조명이 켜져 있음을 의미합니다. 층은 위에서 아래로 순서대로 주어지며, 특히 마지막 줄은 1층을 나타냅니다.
각 행의 처음과 마지막 문자는 계단을 설명하므로 항상 0입니다.

출력:
하나의 숫자 인쇄 – 모든 조명을 끄는 데 필요한 최소 시간입니다.

예:
  <몸>
설명:

첫 번째 예에서 Eric은 먼저 1층의 1번방으로 이동한 다음 — 사다리를 사용하여 2 2층에 있는 방으로.

두 번째 예에서는 먼저 1층 네 번째 방으로 이동하여 오른쪽 계단으로 한 층 올라가고, 2층 네 번째 방으로 들어가 다시 오른쪽 계단으로 올라가서 두 번째 마지막 층에 있는 방입니다.

입력	출력
2 2 0010 0100	5
3 4 001000 000010 000010	12