PLINOVOD

문제

Mirko owns a bakery on the edge of the city. Because of the financial crisis, Mirko's monthly gas bill for the ovens has become too large so he decided to steal gas from a large pipeline near his bakery. 

The land surrounding the bakery can be modelled by an R×C grid so that the pipeline is in the first column and Mirko's bakery in the last column. 

Mirko will connect pipes to the gas pipeline and his bakery. Some parcels of land are inaccessible and Mirko cannot put pipes through them. 

Every path from the pipeline to the bakery starts in a cell in the first column in the grid, ends in the last column, and each cell on the path is connected to the cell diagonally up-right, right or diagonally down-right. 

In order to pull as much gas from the pipeline as possible, Mirko wants to get as many paths to his bakery as possible. The paths may not cross nor touch. In other words, at most one path may pass through any cell. 

Write a program that calculates the largest number of paths Mirko can pull. 

입력

The first line contains two integers R and C (1 ≤ R ≤ 10000, 5 ≤ C ≤ 500), the dimensions of the grid.Each of the following R lines contains a string of C characters, each being a period '.' or the letter 'x'. The letter 'x' represents an inaccessible parcel of land. The first and last cells in each row will be clear.

출력

Output the largest number of paths Mirko can pull from the pipeline to the bakery. 

힌트

[이미지 1]

The grid from the first example, including one possible configuration of paths.