Minimizing Fear in the Elephant's Journey

S country has a zoo which can be represented as an \(N \times M\) grid. The top‐left cell is \((1,1)\) and the bottom–right cell is \((N,M)\). An elephant starts at \((1,1)\) and wants to go home at \((N,M)\). However, there are several mice in the zoo (each located in a distinct cell) and the elephant is scared of mice. The elephant's fear value is defined as the number of different mice it can see along its path.

At any position \((x_1,y_1)\) along its path, the elephant can see a mouse at \((x_2,y_2)\) if and only if \[ |x_1-x_2| + |y_1-y_2| \le 1. \] In other words, from a cell the elephant can see the cell itself and its four adjacent cells (up, down, left and right). Since the elephant is very sleepy, it will only choose a shortest path home, i.e. it only moves right or down at each step. Your task is to help the elephant choose a shortest path that minimizes its overall fear value (i.e. minimizes the number of distinct mice seen).

Note: If a mouse is seen in more than one step along the path it is only counted once.

inputFormat

The first line contains two integers \(N\) and \(M\) representing the number of rows and columns in the grid.

Then follow \(N\) lines, each containing a string of length \(M\). Each character is either R or . where R indicates that there is a mouse in that cell, and . indicates an empty cell.

The top–left cell is at \((1, 1)\) and the bottom–right is at \((N, M)\).

outputFormat

Output a single integer representing the minimum fear value – the minimum number of distinct mice that the elephant can see along a valid shortest path from \((1,1)\) to \((N,M)\).

sample

3 3
R..
...
..R

2