Turning On the Lights

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.

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.

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