Flipping Tiles Puzzle

Farmer John has discovered that high-IQ cows not only produce more milk, but also enjoy mind‐teasing puzzles. In this puzzle, you are given an M × N board (with 1 \le M, N \le 15). Each cell of the board contains a two‐sided tile: one side is black and the other is white. Initially, each tile is either black or white, as specified by the input.

When you flip a tile at position \((i,j)\), it toggles its own color (black becomes white and vice versa), and additionally every tile sharing a common edge with \((i,j)\) is also flipped. That is, if you flip the tile at \((i,j)\), then the tiles at \((i-1,j)\), \((i+1,j)\), \((i,j-1)\), and \((i,j+1)\) (if they exist) will also change color.

Your goal is to determine the minimum number of flips required to make all tiles white. If it is impossible to turn all the tiles white, output \(-1\).

The flipping operation is defined in the following formula (with all operations over \(\mathbb{Z}_2\)):

[ final_{i,j} = init_{i,j} \oplus X_{i,j} \oplus X_{i-1,j} \oplus X_{i+1,j} \oplus X_{i,j-1} \oplus X_{i,j+1} ]

where \(init_{i,j}\) is the initial state of cell \((i,j)\) (with \(1\) representing black and \(0\) representing white), and \(X_{i,j}\) is \(1\) if you flip the tile at \((i,j)\) and \(0\) otherwise.

inputFormat

The first line contains two integers, M and N (1 \le M, N \le 15), representing the number of rows and columns of the board.

Each of the next M lines contains N space-separated integers. Each integer is either 0 (representing a white tile) or 1 (representing a black tile), which indicates the initial state for that cell.

outputFormat

Output a single integer -- the minimum number of flips required to turn all the tiles white. If it is impossible, output -1.

sample

3 3
0 0 0
0 0 0
0 0 0

0