Equalize Board Numbers Game

Blinker is playing a peculiar game on an N × M board. Each cell contains an integer. In each move, Blinker selects two adjacent cells (sharing an edge) and increases both of their numbers by 1.

The goal is to make all numbers on the board equal. Determine the minimum number of moves required to achieve this. If it is impossible to make all numbers equal, output \( -1 \).

Note: A cell is considered adjacent to another if they share a common edge.

Invariant Explanation:

• Color the board in a chessboard pattern with the top-left cell being black. Let \( B \) be the set of black cells and \( W \) be the set of white cells.
• Each move increases one black and one white cell by 1. Hence, the difference \( S_B - S_W \) remains invariant.
• If all cells become \( x \), then:
  • For black cells: \( S_B' = |B| \times x \)
  • For white cells: \( S_W' = |W| \times x \)
  So, the invariant gives: \( S_B - S_W = x(|B| - |W|) \).

Solution Idea:

• Let \( max \) be the maximum number on the board.
• For an even number of cells (i.e. \( |B| = |W| \)), the invariant requires \( S_B = S_W \). If not, output \( -1 \). Otherwise choose \( x = max \) (the minimal possible) and compute moves as \( moves = |B|\times x - S_B \).
• For an odd number of cells, since \( |B| - |W| = 1 \) (assuming top-left is black), we must have \( x = S_B - S_W \). If \( x < max \), it is impossible to reach equality, so output \( -1 \). Otherwise, the required moves is \( moves = |B|\times x - S_B \).

inputFormat

The first line contains two integers \( N \) and \( M \) (the number of rows and columns respectively). The following \( N \) lines each contain \( M \) integers representing the board.

Constraints: All integers fit in a 32-bit signed integer.

outputFormat

Output a single integer representing the minimum number of moves required to make all board numbers equal. If it is impossible, output \( -1 \).

sample

2 2
1 2
3 4

3