题目描述

小 Z 制作了一个机器人，现在有一个 $n \times m$ 的网格图，每个格子上有墙壁或者空地，机器人可以在空地上行动。

机器人初始时在网格图的一个空地位置，用 R 表示，他要走到空地位置 E 上。

系统给出了一串指令，由 U，D，L，R 组成，机器人会按照这个指令移动，如果下一步有墙或者出了边界，则跳过该操作，如果机器人到达终点则会立即停止移动。

每次操作，你可以在指令中任意位置插入一个新的字母，或者删除指令中的任意位置的一个字母，问你最少进行多少次操作，使得机器人能到达 E。

输入格式

第一行，两个正整数 $n, m$。

之后 $n$ 行给出网格图的具体形态。

之后一行，给出一个字符串 $S$，表示指令。

输出格式

一个整数表示答案，数据保证至少存在一组解。

样例

输入数据 1

3 3
R..
.#.
..E
LRDD

输出数据 1

1

输入数据 2

2 4
R.#.
#..E
RRUUDDRRUUUU

输出数据 2

0

输入数据 3

10 10
E#........
.#........
..........
.#........
....#...R.
#.........
..........
..........
..........
#..#......
LLRDLUDDLLLUDDLULLDRLLULLDRLRDLLUD

输出数据 3

4

说明/提示

样例 1 解释

将操作修改为 LRRDD，插入一个 R 即可。

数据范围

对于 $30\%$ 的数据，$1 \le n, m \le 10$。

对于 $100\%$ 的数据，$1 \le n, m \le 50$，$1 \le |S| \le 50$。