## Lights Out!

Lights Out is an electronic game released by Tiger Toys in 1995. (Tiger Toys was later bought by Hasbro in 1998.) The game consists of an R by C grid of lights; when the game starts, some subset (possibly none or all) of these lights are switched on. Pressing one of the lights will toggle it and all adjacent to it (up to four). Diagonal neighbours are not affected. Notice that a light on the edge of the grid will have fewer than four neighbours. The objective of the game is to solve a puzzle: switch all the lights off, preferably in as few button presses as possible. [Wikipedia]

### Input

The input will contain five cases. Each case starts with a line containing two integers R and C (1 ≤ R < C ≤ 5) as described above. The next R lines contain C characters each. A '0' as the ith character in the jth line signifies that the ith button in the jth row starts out off; similarly a '1' signifies that the corresponding light starts out on.

### Output

For each case given in input, in the order given, print a line containing a single integer: the minimum number of button presses required to switch off all of the buttons, or -1 if it is impossible to switch all the lights off regardless of the number of button presses.

3 3
010
111
010
4 5
01000
11010
00001
00110

1
3

### Explanation

In the first sample case, pressing the second button in the second row switches off all lights.
In the second sample case, one presses first the second button in the second row, then the third button in the third row, then the fourth button in the third row.

Point Value: 15 (partial)
Time Limit: 10.00s
Memory Limit: 256M