Turning On the Lights

Time limit2sMemory limit128 MB

Summary

Find the minimum number of bulb presses, each flipping a cell and its 8 neighbors, needed to turn all bulbs on an N×M grid (N,M ≤ 8) on, or report impossibility.

Level: Medium6 of 10
Topics: Bit manipulation, Brute force, Matrix, Simulation
Solved: No attempts yet

Problem

Sejun has an N×M board. The board is divided into 1×1 cells, and each cell contains one light bulb.

Pressing one bulb flips that bulb: an on bulb turns off, and an off bulb turns on. The bulbs are very sensitive, so pressing one bulb also flips the bulbs in the 8 neighboring cells, including horizontal, vertical, and diagonal neighbors.

Given the current state of the board, find the minimum number of bulbs Sejun must press so that every bulb is on.

Input

The first line contains N and M.

Each of the next N lines contains the board state. Both N and M are at most 8. * means the bulb is on, and . means the bulb is off.

Output

Print the minimum number of bulbs that must be pressed to turn every bulb on. If it is impossible, print -1.

Examples4

Example 1
Input
```
3 3
**.
**.
..*
```
Expected output
```
2
```
Example 2
Input
```
1 2
.*
```
Expected output
```
-1
```
Example 3
Input
```
5 5
*****
*...*
*...*
*...*
*****
```
Expected output
```
1
```
Example 4
Input
```
4 4
*...
**..
..**
...*
```
Expected output
```
10
```