Maximum Coins Collection

Alice finds herself on an n × m grid where some cells contain coins. Each cell is either empty (represented by .) or contains a coin (represented by C). Starting at the top-left corner of the grid, Alice wants to reach the bottom-right corner while collecting as many coins as possible. At each step, she may move either right or down.

You can use dynamic programming to solve this problem. The recurrence relation for the maximum coins you'll be able to collect when reaching cell (i, j) is given by:

$$dp[i][j] = \text{coin}(i,j) + \max\{dp[i-1][j],\; dp[i][j-1]\} $$

where \( \text{coin}(i,j) = 1 \) if the cell contains a coin and 0 otherwise. The answer is the value computed at the bottom‐right cell, dp[n-1][m-1].

inputFormat

The first line of input contains two integers n and m representing the number of rows and columns of the grid, respectively.

Each of the next n lines contains a string of length m where each character is either C (indicating a coin) or . (an empty cell).

outputFormat

Output a single integer: the maximum number of coins that can be collected on a path from the top-left to the bottom-right corner by only moving right or down.

## sample

3 4
C.CC
..C.
C..C

4