Minimum Sensors for Art Gallery Surveillance

You are given an art gallery represented as a grid with n rows and m columns. Each cell of the grid is either empty (denoted by '.') or contains an artwork (denoted by 'A'). The artworks need to be monitored by sensors. A sensor placed in an empty cell monitors as well as its four adjacent cells (up, down, left, right) including the cell it is placed in.

Your task is to determine the minimum number of sensors required to monitor all artworks in the gallery. If it is not possible to monitor all artworks, output -1.

The sensor coverage can be expressed by the following formula in \( \LaTeX \):

\[ \text{A sensor placed at } (i,j) \text{ monitors cell } (x,y) \text{ if } |x-i|+|y-j| \le 1. \]

Note: Sensors can only be placed on empty cells (cells with '.') and not on cells containing artworks.

inputFormat

The first line contains two integers n and m (1 ≤ n, m ≤ 1000) representing the number of rows and columns of the gallery. The next n lines each contain a string of length m consisting of characters '.' and 'A', describing the gallery layout.

Input is read from standard input (stdin).

outputFormat

Output a single integer representing the minimum number of sensors required to monitor all artworks. If it is not possible to cover all artworks, output -1.

Output is written to standard output (stdout).

## sample

4 4
....
.AA.
.A..
....

2