题目背景

在一座环形导航大厅中，每块地砖上都画着一个方向箭头。沿着箭头不断前进时，越过大厅边界的人会从相对的一侧重新出现。设计者希望无论从哪块地砖出发，最终都能沿着箭头回到原来的位置。现在部分箭头的方向出现了错误，你需要用最少的修改次数修复整块方向板。

题目描述

有一个由 $H$ 行 $W$ 列组成的方向板。每个格子中有一个箭头，方向为左、右、上、下之一，分别用字符 L、R、U、D 表示。

格子的坐标从 $0$ 开始编号，左上角为 $(0,0)$。如果当前位于格子 $(r,c)$，则按照该格子中的箭头移动：

• L：移动到 $(r,c-1)$；
• R：移动到 $(r,c+1)$；
• U：移动到 $(r-1,c)$；
• D：移动到 $(r+1,c)$。

方向板的每一行和每一列都是循环的。也就是说，当移动越过边界时，会从相对的一侧出现。例如，在一个 $5\times 5$ 的方向板中，从 $(3,0)$ 向左移动后会到达 $(3,4)$。

称一个方向板是合法的，当且仅当从任意一个格子出发，按照箭头不断移动，都能在经过若干次移动后回到出发格子。

你可以修改任意格子中的箭头方向，每修改一个格子计作一次操作。请计算将给定方向板变为合法方向板所需的最少操作次数。

例如，下面的方向板经过两次修改后即可变为合法方向板：

原方向板      一种合法的修改结果
RRRD          RRRD
URLL          URLR
LRRR          LRLR

其中修改了坐标 $(1,3)$ 和 $(2,2)$ 处的箭头。

输入格式

第一行包含两个整数 $H,W$，分别表示方向板的行数和列数。

接下来 $H$ 行，每行包含一个长度为 $W$ 的字符串，描述方向板中各格子的箭头方向。

输出格式

输出一个整数，表示将方向板变为合法方向板所需的最少箭头修改次数。

数据范围

• $1\le H\le 15$；
• $1\le W\le 15$；
• 输入字符串仅包含字符 L、R、U、D。

样例

样例 1

4 4
RRRD
URDD
UULD
ULLL

0

该方向板本身已经合法，因此不需要修改任何箭头。

样例 2

3 4
RRRD
URLL
LRRR

2

一种最优方案如题目描述中的示意所示，只需修改两个箭头。

样例 3

3 3
RRD
URD
ULL

2

例如，从格子 $(1,1)$ 出发时，原方向板无法回到该格子；最少需要修改两个箭头。

样例 4

2 6
ULRLRD
UDDLRR

4

样例 5

4 8
UDLRLDLD
DLDLLDLR
LLLLLDLD
UUURRRDD

9

样例 6

15 15
UDUDUUDUDUDUDUR
LLLLDUUDRDLUDRU
DLLDLDURDURUDDL
UDUDUUDUDUDUDUR
LLLLDUUDRDLUDRU
DLLDLDURDURUDDL
UDUDUUDUDUDUDUR
LLLLDUUUDDLUDRU
DLLDLDURDURUDDL
UDUDUUDUDUDUDUR
LLLLDUUDRDLUDRU
DLLDLDURDURUDDL
UDUDUUDUDUDUDUR
LLLLDUUDRDLUDRU
RRRDLDURDURUDDR

73

说明

原题采用 Topcoder 函数调用形式。本题已改为标准输入、标准输出形式，便于在 Hydro OJ 中直接评测。