침략자 진아

행성은 $N$행 $M$열의 격자로 주어진다. 각 칸은 빈 공간($0$) 또는 마을($1$)이다. 빈 공간에만 독주머니를 정확히 $2$개 설치해야 한다.

독은 매초 상하좌우로 인접한 칸으로 퍼진다. 마을이 중독되면 그와 인접한 마을도 $1$초 후에 중독되므로, 독의 확산은 격자의 모든 칸을 통과하는 이동과 같다. 마을 $(x, y)$가 중독되는 시각은 두 독주머니까지의 맨해튼 거리 중 작은 값과 같고, 모든 마을이 중독되는 시각은 그 값들의 최댓값과 같다. 이 최댓값을 최소로 만드는 배치를 구해야 한다.

행 번호는 $0$부터 $N-1$까지, 열 번호는 $0$부터 $M-1$까지이며, 가장 위의 가장 왼쪽 칸이 $(0, 0)$이다. 독주머니를 설치할 수 없는 경우는 주어지지 않는다.

첫째 줄에 정수 $N$과 $M$이 공백으로 구분되어 주어진다. ($2 \le N, M \le 20$)

다음 $N$개의 줄에 길이가 $M$인 문자열이 주어진다. 각 문자는 $0$ 또는 $1$이며, $0$은 빈 공간, $1$은 마을을 의미한다.

독주머니 $2$개를 최적의 빈 칸에 설치했을 때, 모든 마을이 중독되는 데 걸리는 최소 시간을 초 단위로 출력한다.