조명 배치

윤이는 최근에 Mazecraft라는 게임을 즐기고 있다. Mazecraft는 $H\times W$ 직사각형 격자 위에 미로를 그리는 게임이다. 격자의 맨 왼쪽 위 격자칸의 좌표는 $(1,1)$, 맨 오른쪽 아래 격자칸의 좌표는 $(H,W)$이다. 각 격자칸은 빈칸이거나 벽이며, 빈칸에는 조명을 설치할 수 있다. 각 조명은 양의 정수인 밝기를 가지고 있다.

격자에서 두 빈칸 사이의 거리는 한 빈칸에서 시작해서 인접한 빈칸으로 이동하는 것을 반복하여 다른 빈칸에 도달하는 데 필요한 최소 이동 횟수이다. 만약 한 빈칸에서 시작해서 다른 빈칸으로 도달할 수 없다면, 두 빈칸 사이의 거리는 정의되지 않는다.

Mazecraft는 독특한 조명 시스템을 갖추고 있는데, 그 원리는 다음과 같다.

• 어떤 빈칸에 밝기가 $c$인 조명 $L$이 설치되어 있다고 하자. 조명 $L$은 빈칸마다 정수 값의 영향력을 미치며, 영향력의 크기는 조명에서 멀어질수록 작아진다. 조명 $L$이 각 빈칸에 미치는 영향력은 구체적으로 다음과 같이 계산된다.

  • $L$이 위치한 격자칸에 미치는 영향력은 $c$이다.
  • $L$과의 거리가 $1$인 격자칸에 미치는 영향력은 $c-1$이다.
  • $\dots$
  • $L$과의 거리가 $c-2$인 격자칸에 미치는 영향력은 $2$이다.
  • $L$과의 거리가 $c-1$인 격자칸에 미치는 영향력은 $1$이다.
  • 그 외의 빈칸에는 영향력을 미치지 않는다.

• 어떤 빈칸의 밝기는, 모든 조명들이 이 빈칸에 미치는 영향력 중 최댓값이다. 만약 빈칸에 영향력을 미치는 조명이 하나도 없으면 그 빈칸의 밝기는 $0$이다.

윤이는 인터넷에서 마음에 드는 미로를 발견해서 Mazecraft에서 따라 만들어 보기로 했다. 그런데 윤이가 발견한 미로의 설계도에는 모든 빈칸의 밝기가 기록되어 있지만 조명의 위치는 기록되어 있지 않았다. 윤이는 최소 개수의 조명을 설치해서, 벽의 배치와 빈칸의 밝기가 설계도와 동일한 미로를 만들고자 한다. 설계도와 동일한 미로를 만드는 것이 가능한지 판별하고, 만약 가능하다면 필요한 조명의 최소 개수를 구하시오.

첫 번째 줄에는 정수 $H$, $W$가 주어진다. $(1\le H,W\le 1\ 000)$

다음 $H$개의 줄에는 미로의 밝기 정보가 주어진다. 각 줄에는 $W$개의 정수가 공백으로 구분되어 주어진다. 이 중 $i$번째 줄의 $j$번째 정수는 격자칸 $(i,j)$의 밝기를 나타내며, 밝기는 $0$ 이상 $10\ 000$ 이하의 정수이다. 만약 해당 격자칸에 벽이 있다면 대신 $-1$이 주어진다.

만약 설계도와 동일한 미로를 만드는 것이 가능하다면, 그러한 미로를 만드는 데 필요한 조명의 최소 개수를 출력한다. 만약 미로를 만드는 것이 불가능하다면, $-1$을 출력한다.