Description

A perfect cyclic grid is defined as follows: starting from any position, by following the arrows you will eventually return to the starting position. If a cyclic grid is not perfect, you may arbitrarily modify the arrow in any cell until it becomes perfect. For example, in the figure below, the grid on the left is not perfect, because only starting from $(1, 1)$, $(1, 2)$, $(2, 0)$, $(2, 3)$ will return to the starting position. By modifying two arrows, you obtain the grid on the right, which is perfect.

Given a cyclic grid, compute the minimum number of cells you need to modify to make it perfect.

Input Format

The first line contains two integers $R$ and $C$, the numbers of rows and columns of the cyclic grid. The next $R$ lines each contain $C$ characters, each being L, R, U, or D, indicating left, right, up, and down.

Output Format

Output a single integer, the minimum number of cells that need to be modified to make the given cyclic grid perfect.

4 4
RRRD
URDD
UULD
ULLL

0

3 4
RRRD
URLL
LRRR

2

Hint

Constraints

30% of the testdata: $1 \le R, C \le 7$.

100% of the testdata: $1 \le R, C \le 15$.

Translated by ChatGPT 5