조각상

센트럴 시티는 유명한 조각상 공원으로 잘 알려져 있다. 공원은 격자로 배치되어 있고, 각 격자 칸에는 조각상이나 공원의 물 시설이 들어 있다(그림 L.1a 참고). 조각상은 모양과 크기가 제각각인데, 여기에 문제가 있다. 일부 조각상이 너무 커서 공원을 둘러싼 주요 산책로인 도로 N, E, S, W에서 다른 조각상들을 보는 시야를 가리기 때문이다. 공원 조각상 관리인은 Milo D. Venus이고, 그는 이 산책로 중 두 곳에서 방문객들이 모든 조각상을 볼 수 있도록 일부 조각상을 옮기려고 한다. 그가 생각한 한 가지 방법은 공원의 한 모서리를 고른 뒤, 그 모서리에서부터의 대각선 거리 순서대로 격자의 대각선을 따라 조각상을 배치하고, 물 시설 칸은 건너뛰는 것이다. 가장 작은 조각상은 첫 번째 대각선에 놓인다(그곳에 물 시설이 없다고 가정한다). 그다음으로 작은 조각상들은 두 번째 대각선에 놓인다(이 대각선에 있는 물 시설 칸의 수에 따라 $0$, $1$, $2$개가 될 수 있다). 그다음으로 작은 조각상들은 세 번째 대각선에 놓이고, 이런 식으로 계속된다. 다만 이 방식에는 선택할 것이 많다. 예를 들어 도로 N과 W를 따라 가장 잘 보이게 하려면 그림 L.1b의 대각선을 사용하여 가장 작은 조각상을 대각선 $a$에, 그다음으로 작은 조각상을 대각선 $b$에, 그다음으로 작은 세 조각상을 대각선 $c$에, 그다음으로 작은 두 조각상을 대각선 $d$에 놓는 식이다. 도로 W와 S를 따라 가장 잘 보이게 하려면 그림 L.1c의 대각선을 사용하여 가장 작은 조각상을 대각선 $a$에, 그다음으로 작은 두 조각상을 대각선 $b$에, 그다음으로 작은 세 조각상을 대각선 $c$에, 그다음으로 작은 조각상을 대각선 $d$에 놓는 식이다. 조각상을 두 개보다 많이 놓을 수 있는 대각선 안에서는 그 조각상들을 어떤 순서로든 배치할 수 있어서 선택지가 더 많아진다.

그림 L.1: 조각상 공원. (b)와 (c)는 대각선의 두 가지 가능한 배치를 보여준다

이렇게 유연성이 많으니 옮겨야 하는 조각상 수를 최소로 하는 방식을 고르는 것이 자연스러워 보이지만, 어떤 방식이 가장 좋은지는 바로 분명하지 않다. Milo는 매우 유능한 관리자이고 매력도 넘치지만(정말로 사람을 녹이는 매력이다), 이런 문제를 푸는 데는 그리 뛰어나지 않다. 시간을 내어 그를 도와줄 수 있는가?

입력은 공원 격자의 행 수와 열 수를 나타내는 두 양의 정수 $n$ $m$ ($n,m \leq 50$)으로 시작한다. 그다음 $n$개의 행이 각각 $m$개의 정수를 포함한다. $i$번째 행의 $j$번째 값은 공원 격자의 $i$행 $j$열에 있는 것을 나타낸다. 이 값이 양수이면 그 높이의 조각상을, $-1$이면 물 시설을 나타낸다. 두 조각상의 높이가 같지 않다.

위에서 설명한 방식으로 조각상을 배치하는 모든 방법 중 옮겨야 하는 조각상 수의 최솟값을 출력한다.