Lights Out Puzzle

You are given a grid of lights, each of which is either off (0) or on (1). When you toggle (or press) a light, that light and its four adjacent neighbors (up, down, left and right) will have their states switched (0 becomes 1 and 1 becomes 0). The task is to determine the minimum number of toggles needed so that all lights are on.

Example:

Initial grid:
0 1 1
1 0 0
1 0 1
Toggle the middle light (row 2, column 2 using 1-indexing):
0 0 1
0 1 1
1 1 1
Toggle the top-left light (row 1, column 1):
1 1 1
1 1 1
1 1 1

The answer in this example is 2 toggles.

inputFormat

The first line contains two integers m and n (1 ≤ m, n ≤ 10) representing the number of rows and columns of the grid.

Each of the next m lines contains n integers separated by spaces, each being either 0 or 1, representing the initial state of the grid.

It is guaranteed that a solution exists.

outputFormat

Output a single integer, the minimum number of toggles required to turn all lights on.

sample

3 3
0 1 1
1 0 0
1 0 1

2