Maximum Parking Spots

The city of Zagreb plans to build a new parking lot on a rectangular piece of land. The land is an \(N\times M\) grid divided into \(N\) rows and \(M\) columns, and each cell is denoted by \((i,j)\) for the \(i\)th row and \(j\)th column.

Some cells have pre-determined water features (denoted by a W). The remaining cells can be converted either into a parking spot or a driveway. Note that the entrance of the parking lot is at cell \((1,1)\) (upper left corner) and must be a driveway.

Cars can move in four directions (up, down, left, right) from one cell to an adjacent cell, as long as the next cell is within the grid.

A construction scheme is valid if it satisfies the following:

• The cell \((1,1)\) is a driveway.
• Every car parked in a parking spot has a path to the entrance \((1,1)\) such that aside from its starting cell, the path goes only through driveways. (In other words, if a cell is designated as a parking spot, then at least one of its adjacent cells must be a driveway which is connected (via driveways) to the entrance.)

Let the set of available cells (i.e. non-water cells) be \(A\). In any valid scheme, the available cells are partitioned into a set \(D\) that are designated as driveways and a set \(P = A\setminus D\) of parking spots. The conditions above force \(D\) to be a connected dominating set that contains cell \((1,1)\) (when considering the grid graph induced by available cells) – that is, every cell in \(P\) is adjacent to at least one cell in \(D\).

Your task is to choose \(D\) (and consequently \(P\)) so that the number of parking spots \(|P| = |A| - |D|\) is maximized (or equivalently, \(|D|\) is minimized). Compute and output the maximum number of parking spots in any valid scheme.

Note: Because determining the minimum connected dominating set is NP-hard in general, the grid size in the input will be small.

inputFormat

The first line contains two integers \(N\) and \(M\) (the number of rows and columns respectively).

Then follow \(N\) lines, each with a string of length \(M\). Each character is either . (denoting an available cell) or W (denoting a cell with a water feature). It is guaranteed that the cell at \((1,1)\) (the first character of the first line) is available (i.e. .).

outputFormat

Output a single integer: the maximum number of parking spots that can be built on the available cells for a valid construction scheme.

sample

2 2
..
..

2