Bakery

Time limit1sMemory limit256 MB

Summary

Given a grid where pipelines move from the first column to the last column stepping right, diagonal-up-right or diagonal-down-right without sharing cells, find the maximum number of vertex-disjoint such paths.

Level: Medium7 of 10
Topics: Graph, Greedy, Dynamic programming
Solved: No attempts yet

Problem

Baker Wonung wants to connect pipelines from a nearby gas pipe to his bakery. The area around the bakery is represented as an R x C grid. The first column is the nearby gas pipe, and the last column is Wonung's bakery.

Each cell is either empty or occupied by a building. A pipeline cannot pass through a building cell.

Every pipeline must start in one cell of the first column and end in one cell of the last column. From a cell, it may continue only to the cell directly right, diagonally up-right, or diagonally down-right. Connections are drawn between the centers of adjacent cells.

Wonung wants to install as many pipelines as possible. Different pipelines cannot pass through the same cell. Given the grid, find the maximum number of pipelines that can be installed.

Input

The first line contains R and C. (1 <= R <= 10,000, 5 <= C <= 500)

The next R lines describe the grid around the bakery. . means an empty cell, and x means a cell occupied by a building. The first and last columns are always empty.

Output

Print the maximum number of pipelines that can be installed.

Examples2

Example 1
Input
```
5 5
.xx..
..x..
.....
...x.
...x.
```
Expected output
```
2
```

Example 2

Input

6 10
..x.......
.....x....
.x....x...
...x...xx.
..........
....x.....

Expected output