Bakery

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.

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.

Print the maximum number of pipelines that can be installed.