조명 배치

윤이는 최근 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$을 출력한다.