You are trying to refirbish a factory for your own use.

The factor has an ~n \times m~ grid of conveyors. Each conveyor has a set direction. If an object is placed on top of it, the conveyor will move that object in its set direction.

You want to rearrange the conveyors such that the an object placed on the top left conveyor will eventually reach the bottom right conveyor. To do this, you can rotate any conveyor ~90^\circ~, for a cost of ~\$1~.

What is the minimum cost to rearrange the conveyors in this way?

Input

The first line contains integers ~n,m~, representing the dimension conveyor grid.

The following ~n~ lines contain ~m~ space separated characters. These will be either U, D, L or R, representing the initial direction of each conveyor.

Output

An integer containing the minimum cost to rearrange the conveyors such that an object placed on the top left will reach the bottom right.

Constraints

• ~1 \le n,m~
• ~1 \le n \times m \le 2 \times 10^6~

Subtask 1 - 1 Point

• ~n = 1~

Subtask 2 - 1 Point

• No additional constraints

Example - Subtask 1

Input

1 5
R R D L D

3

Example - Subtask 2

Input

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

Output

5