Dark Room

One day Harry Potter came to a magic room, in which there are some shadow monsters sent by the black wizard waiting for him. Fortunately, shadow monsters can only live in areas where there are no lights shining, there are n*m lamps on the roof of the room, every little lamp can only illuminate the scope of the fixed area, and all the area of lights shining don't overlap, some lamps on, some lamps off, the areas below the closed lamps will appear the shadow, and in these areas shadow monsters will attack Harry Potter. Now Harry Potter comes to you and gives you the previous state of the room lights, Harry Potter can control the light switch in a remote place .The state of a light will change as follows: if a lamp state changed, the state of the lights which before it, after it, left to it or right to it will all change. Your task is to calculate how many times we need at least to turn on all the lights by changing the state of the lamps.

in the first line there are two integers, n (1 < = n < = 100) and m (1 < = m < = 15), stands for there are n lines, each line have m data, 0 stands for the lights off, 1 stands for the lights on.

for each group of input data, output an integer stands for the minimum number we need to change the state of the lights to put all the lights on, if we can't turn on all the lamps, output 'no solution'.

3 3
1 0 1
0 0 0
1 0 1

1

2011 Multi-University Training Contest 10 - Host by HRBEU