치즈

직사각형 판은 정사각형 칸으로 이루어져 있고, 그 위에 얇은 치즈가 놓여 있다. 판의 가장자리에는 치즈가 없으며, 치즈 안에는 하나 이상의 구멍이 있을 수 있다.

치즈를 공기 중에 두면 공기와 접촉한 칸은 한 시간이 지난 뒤 녹아 사라진다. 치즈 내부의 구멍에는 처음에는 공기가 없지만, 구멍을 둘러싼 치즈가 녹아 외부와 연결되면 그때부터 공기가 들어간다. 아래 그림에서는 c로 표시된 부분만 한 시간 뒤 녹아 없어지고, 구멍을 둘러싼 치즈는 아직 녹지 않는다.

<그림 1> 처음 치즈 모양

다시 한 시간이 지나면 <그림 2>에서 c로 표시된 부분이 녹아 없어져 <그림 3>과 같은 모양이 된다.

<그림 2> 한 시간 뒤의 치즈 모양

<그림 3> 두 시간 뒤의 치즈 모양

<그림 3>은 처음 상태에서 두 시간이 지난 모습이다. 이 상태에서 남은 조각들은 한 시간이 더 지나면 모두 녹으므로, 전체 치즈가 사라지는 데 걸리는 시간은 세 시간이다. 녹는 과정에서 치즈가 여러 조각으로 나뉠 수도 있다.

판의 크기와 치즈 배치가 주어질 때, 치즈가 모두 녹는 데 걸리는 시간과 모두 녹기 한 시간 전에 남아 있던 치즈 칸의 수를 구하시오.

첫째 줄에 판의 세로 길이 N과 가로 길이 M이 양의 정수로 주어진다. N과 M은 각각 최대 100이다.

이어서 N개의 줄에 위쪽 행부터 차례대로 판의 상태가 주어진다. 치즈가 없는 칸은 0, 치즈가 있는 칸은 1이며, 한 줄의 값들은 공백 하나로 구분된다.

첫째 줄에 치즈가 모두 녹아 없어지는 데 걸리는 시간을 출력한다.

둘째 줄에 모두 녹기 한 시간 전에 남아 있던 치즈 칸의 수를 출력한다.