Magic Checkerboard

Consider an $n \times m$ checkerboard. Write a positive integer in every cell. In each column the values must increase strictly from top to bottom, and in each row they must increase strictly from left to right.

A magic checkerboard has one more rule. Two cells that share only a corner must hold numbers of different parity, one even and one odd. The board below is not magic, because 2 and 4 share only a corner and are both even.

The $4 \times 4$ board above is a valid magic checkerboard. You are given a partially filled board. Fill the empty cells so that the sum of all values is as small as possible.

The input is a single test case. The first line has two space separated integers $n$ and $m$ ($1 \le n, m \le 2000$), the number of rows and the number of columns of the board. Each of the next $n$ lines has $m$ space separated integers $c$ ($0 \le c \le 2000$), the contents of the board. A zero marks an empty cell that you must fill. You may write any positive integer in an empty cell as long as the finished board is a valid magic checkerboard. The values you write are not capped at 2000 and do not have to be distinct.

Print one integer, the smallest sum you can reach by replacing every zero with a positive integer so that the board becomes a valid magic checkerboard. Print $-1$ if no such board exists.