마법의 체스판

$n \times m$ 크기의 체스판이 있다. 각 칸에 양의 정수를 하나씩 적는데, 같은 열에서는 위에서 아래로 갈수록 값이 엄격하게 커져야 하고, 같은 행에서는 왼쪽에서 오른쪽으로 갈수록 값이 엄격하게 커져야 한다.

마법의 체스판에는 조건이 하나 더 있다. 꼭짓점만 맞닿은 두 칸에 적은 수는 홀짝이 서로 달라야 한다. 아래 판은 $2$와 $4$가 꼭짓점만 맞닿아 있으면서 둘 다 짝수이므로 마법의 체스판이 아니다.

위의 $4 \times 4$ 판은 올바른 마법의 체스판이다. 일부만 채워진 판이 주어진다. 빈 칸을 모두 채워서 전체 합을 가장 작게 만들어라.

입력은 테스트 케이스 하나로 이루어진다. 첫 줄에 판의 행 수 $n$과 열 수 $m$이 공백으로 구분되어 주어진다 ($1 \le n, m \le 2000$). 다음 $n$개 줄에는 판의 내용을 나타내는 정수 $c$가 $m$개씩 공백으로 구분되어 주어진다 ($0 \le c \le 2000$). $0$은 직접 채워야 하는 빈 칸을 뜻한다. 완성된 판이 올바른 마법의 체스판이기만 하면 빈 칸에는 어떤 양의 정수든 적을 수 있다. 적는 수가 $2000$ 이하일 필요는 없고, 서로 다를 필요도 없다.

$0$인 칸을 모두 양의 정수로 채워 올바른 마법의 체스판을 만들 때 나올 수 있는 합의 최솟값을 정수 하나로 출력한다. 조건을 만족하도록 채울 수 없으면 $-1$을 출력한다.