불 켜기

세준이는 N×M 크기의 보드를 가지고 있습니다. 보드는 1×1 크기의 칸으로 나뉘어 있고, 각 칸에는 전구가 하나씩 있습니다.

전구 하나를 누르면 그 전구의 상태가 반전됩니다. 켜져 있던 전구는 꺼지고, 꺼져 있던 전구는 켜집니다. 전구는 매우 민감해서, 어떤 전구를 누르면 상하좌우와 대각선을 포함한 주변 8칸의 전구도 함께 반전됩니다.

현재 전구의 상태가 주어질 때, 모든 전구를 켜기 위해 눌러야 하는 전구 수의 최솟값을 구하세요.

첫째 줄에 N과 M이 주어집니다.

둘째 줄부터 N개의 줄에 보드의 상태가 주어집니다. N과 M은 8 이하입니다. *는 켜진 전구, .는 꺼진 전구를 의미합니다.

첫째 줄에 모든 전구를 켜기 위해 눌러야 하는 전구 수의 최솟값을 출력합니다. 불가능하면 -1을 출력합니다.