There is a n x m grid. For each cell (i, j) there is exactly a bulb(on or off) on it.
If the bulb on (i, j) is switched(on to off/off to on) by you, all the bulbs on (i-1, j), (i, j-1), (i, j+1) and (i+1, j) will also be switched magically(it the bulb exists).
Now you are give the state of all the bulbs initially. You need to output the minimum number of the bulbs you need to switch such that all the bulbs are on. There may be no such a plan which makes all the bulbs on.
For example, consider a 3 x 3 grid and the bulbs on (1, 3), (3, 2), (3,3) are on in the beginning. The optimal choice to switch the bulbs on (1, 1), (3, 2) and (3, 3).
0 0 1 1 1 1 1 1 1 1 1 1
0 0 0 =======> 1 0 0 =======> 1 1 0 =======> 1 1 1
0 1 1 0 1 1 1 0 0 1 1 1
switch (1,1) switch (3,2) switch (3,3)
The first line contains two integers n, m (1 ≤ n x m ≤ 20) – the gridsize of the grid.
The following n lines contain m integers each, the j-th element in the i+1-th line sij is state(1 represents on and 0 represents off) of the bulb on (i, j) (0 ≤ sij ≤ 1).
Output the minimum number of the bulbs you need to switch such that all the bulbs are on. If there is no such plan which meets the condition, output "no solution" instead.
And then output a newline('\n').