Ant Cheese Exploration

You control an extraordinary ant with a passion for cheese – and you cannot get enough of it! In a large kitchen, a brand‐new piece of cheese has been discovered, represented as a grid with N rows and M columns. The rows are numbered from 1 to N (top to bottom) and the columns from 1 to M (left to right). Each cell in the grid is either cheese (denoted by a character 'C') or a hole (denoted by a character 'H'). It is guaranteed that the top‐left cell (1,1) and the bottom‐right cell (N,M) always contain cheese.

You plan to dispatch some of your sub‐ants – exactly K of them – from the top‐left to the bottom‐right cell. Each sub‐ant moves only right or down along a path. Moreover, the chosen paths must be non–crossing. Formally, one can number the K paths from 1 to K in such a way that at no cell does a lower–numbered ant make a right move while a higher–numbered ant makes a down move.

There is one more twist. You want the selected paths to be sufficiently "different" in the following sense: For every pair of distinct ants (say ant i and ant j with i<j), there must exist at least one cell (r,s) that is a hole (i.e. its contents is H) such that at some moment the upper ant is in column s in some row strictly less than r while the lower ant is in column s in some (not necessarily simultaneous) moment with row strictly greater than r. In other words, every two ants must approach some hole from opposite sides.

Your task is to determine the maximum number K of sub–ants that can be dispatched so that there exist K non–crossing paths from (1,1) to (N,M) satisfying the separation requirement. It can be shown that an optimal solution always exists.

Observations and a Hint:

Since the paths are monotonic (only right and down moves) and non–crossing, in every fixed column the sub–ants appear in a certain order from top to bottom. For each adjacent pair among the K ants there must be at least one column where the vertical gap between their positions contains a hole. Because you have complete freedom in designing the paths (subject to monotonicity and starting/ending positions), it turns out that the maximum possible K is determined by the total witnessing capacity of the grid. In a given column j consider the set of rows where there is a hole (i.e. a cell with 'H') and that lie strictly between 1 and N. Using a greedy construction one may show that the maximum number of gaps (i.e. adjacent ant pairs that can be separated in this column) that this column can witness is computed by setting cur = 1 and then for each hole at row h with h > cur and h < N one can increment the column’s capacity by 1 and update cur = h+1. Let f(j) denote this capacity for column j.

Since different columns (possibly even the same column) may be used to witness the separation for different adjacent pairs of ants, the necessary and sufficient condition for the existence of K valid paths is that

Also, because the paths pass through rows numbered 1 through N, certainly K cannot exceed N. Therefore, the maximum valid K is

Your program should compute and output this value of K.

inputFormat

The first line contains two integers N and M (2 ≤ N, M ≤ 1000), representing the number of rows and columns of the grid.

The following N lines each contain a string of length M consisting only of the characters C and H. C represents cheese and H represents a hole. It is guaranteed that the top–left cell and the bottom–right cell are always C.

outputFormat

Output a single integer – the maximum number K of valid, non–crossing paths from (1,1) to (N,M) satisfying the separation condition.

Note: The answer is given by
$K = \min\Bigl(N, \;\Bigl(\sum_{j=1}^{M} f(j)\Bigr) + 1\Bigr)$,
where for each column j, f(j) is computed with the following greedy procedure:

cur = 1
count = 0
for each hole h in column j (in increasing order) {
    if (h > cur and h < N) {
         count++
         cur = h + 1
    }
}

sample

4 4
CCCC
CHCC
CCCC
CCCC

2