Forest
In central Russia, forests sometimes expand into arable land. To keep these areas separate, a fence is built between the forest and the field. As the forest grows, the fence needs to be adjusted accordingly.
The area is represented as a map with N×M cells. Each cell is either forest, field, or fence. The fence cells have the following characteristics:
The fence is connected, meaning you can reach any fence cell from any other by moving through adjacent cells (adjacent cells share a side).
The fence is minimal by inclusion, so removing any cell from the fence (turning it into forest or field) will cause it to no longer function as a fence.
The fence separates the forest and the field, with all cells to the left of the fence being forest and all cells to the right being field.
The fence can be described as a sequence of cells where each subsequent cell is to the left, right, or below the previous one.
You can use all the cells initially occupied by the fence, as well as cells that are at most one cell to the right of the initial fence cells (using the leftmost and rightmost columns of the map is not allowed). Your task is to construct a fence of minimal length that meets all the above conditions. It is known that the initial fence is valid, and the leftmost column of the map is entirely forest, while the rightmost column is entirely field.
Input
The first line of the input contains two numbers N and M - the dimensions of the map (1 ≤ N, M ≤ 1000). Following this are N rows with M characters each, representing the initial positions of the forest, field, and fence. Forest cells are marked with "F", field cells with ".", and fence cells with "#".
Output
Output a single number - the minimum length of the fence that can be achieved.