You are given an ~n \times m~ grid, each with a corresponding direction:

• U - up
• D - down
• L - left
• R - right

A ball is placed somewhere on the grid. Each second, the ball moves 1 place in the direction of its current cell.

What is the minimum number of cells you have to change, such that the ball will remain on the grid forever, no matter where the ball is initially placed.

Input

The first line contains integers ~n,m~, which denote the dimensions of the grid. The next ~n~ lines contain ~m~ characters, where the ~j~-th character on the ~i~-th line represents the direction of cell ~(i, j)~.

Output

The total number of cells you need to change.

Constraints

• ~1 \le n,m \le 200~

Example 1

Input

4 4
D U R R
D L U L
D D D D
D U R L

Output

3

Example 2

Input

5 10
R L R U D R D L D R
L L D L L D R D L D
D R L L R D U R D D
R U L U R L L L U L
U U U D L D U L L D

Output

6