Parking

Time limit3sMemory limit1024 MB

Summary

On a grid with fixed fountains, mark the most free cells as parking so each spot reaches the top-left exit without being blocked by other spots.

Level: Hard8 of 10
Topics: Dynamic programming, Bit manipulation, Graph
Solved: No attempts yet

Problem

The city government plans to build a new parking lot on a rectangular plot that can be viewed as a grid with $N$ rows and $M$ columns. To attract visitors and raise revenue, the mayor has decided to place fountains, wells, water taps, and other kinds of fountains on certain fixed cells. The remaining cells are for vehicle movement, and they will be rearranged into one of two types:

parking cells, or
free-movement cells for vehicles.

A vehicle can move to an adjacent cell in one of four directions (north, south, east, or west) in each step. The parking lot must be built so that from every parking cell, a vehicle can reach the entrance and exit in the top-left cell (the intersection of the first row and the first column) at any time. In other words, parked vehicles must not block other vehicles. Each parked vehicle must be able to leave the lot without moving any other parked vehicle.

Find the maximum number of parking cells that can be made on the given plot.

Input

The first line contains natural numbers $N$ and $M$ ( $1 \le N \le 6$ , $1 \le M \le 100$ ), the number of rows and columns of the plot.

Each of the next $N$ lines contains $M$ characters describing the plot:

The character 'x' marks a cell where a fountain will be built.
The character '.' marks a cell that will be rearranged for parking.

Output

Print one line containing the maximum possible number of parking cells.

Hint

This explains the fourth sample. One possible arrangement of parking cells (P marks a parking cell) is shown below.

.PPPx
....x
.Px.P
PxP.x

Examples4

Example 1
Input
```
3 3
...
.x.
...
```
Expected output
```
2
```
Example 2
Input
```
3 3
...
..x
...
```
Expected output
```
4
```
Example 3
Input
```
3 6
.x..x.
..x.x.
......
```
Expected output
```
3
```
Example 4
Input
```
4 5
....x
....x
..x..
.x..x
```
Expected output
```
7
```