问题描述

小明自己发明了一个电子的滑冰游戏如下：

初始时给你一个大小为 $n \times n$ 的地图，地图由#、*、数字符号（$0$至$9$）组成，其中地图的边界一定都是#，且#只出现在边界。

下图是一个 $n = 7$ 的例子：

#######
#12345#
#4**12#
#67*27#
#*08*1#
#11129#
#######

定义坐标 $(a, b)$ 为第 $a$ 行第 $b$ 列。

#代表不可破坏的墙壁，*代表可敲碎的冰块，而数字和得分有关。

游戏开始时，游戏会随机告诉你游戏角色所在的起始位置。接著每一步有 $2$ 种可能操作：

第一种是滑行的操作。可以选择上下左右四个方向的任一个方向滑行，一但滑行开始后，只当碰到墙壁或是冰块时才会停下来。若选择的方向的下一格就是墙壁或是冰块，就会留在原地。滑行完后，游戏的得分就会增加滑行完后游戏角色停下的格子上的数字，增加完后此数字会变为$0$。

第二种操作是敲碎冰块的操作。此操作只能在上一步是滑行且挡住游戏角色的是冰块而不是墙壁时执行，执行后，上一步挡住游戏角色的冰块就会被敲碎，之后此冰块的位置会变为数字$0$的格子。

设计玩此游戏后小明超想知道，若游戏角色起始位置在座标 $(x, y)$，且只能移动恰 $m$ 步，游戏结束时最多能得多少分。

但这问题实在太难了，于是小明先拜託你帮忙写一个程序，模拟小明所执行的操作并计算游戏结束时的总得分。其中，向上下左右四个方向滑行的操作依序用大写英文字母$U,D,L,R$表示；而敲碎冰块的操作由大写英文字母$B$表示。保证当执行敲碎冰块操作时，上一步一定是滑行且在上一步挡住游戏角色的一定冰块。

输入格式

输入第一行包含一个正整数 $n$，代表地图大小。

接着有 $n$ 行，每行有一个长度为 $n$ 的字串，这 $n$ 行代表著游戏的地图。

下一行有两个正整数 $x, y$，代表游戏角色起始位置在 $(x, y)$。

再下一行有一个正整数 $m$，代表你要模拟的操作次数。

之后还有一行，包含长度为 $m$ 的由大写英文字母组成的字串，此字串的第 $i$ 个字母代表你要模拟的第 $i$ 个操作。

输出格式

输出包含一行，包含一个整数。代表按照输入的操作模拟时，游戏结束后的得分。

数据范围

对于 $50\%$ 的数据，模拟的操作中 不包含 敲碎冰块的操作。

对于所有测试数据都满足 $3 \le n \le 20, 1 \le m \le 500$，起始位置一定是数字的格子。

样例输入1

7
#######
#12345#
#4**12#
#67*27#
#*08*1#
#11129#
#######
2 4
5
DDRUL

样例输出1

9

样例1解释

游戏角色的起始位置是座标 $(2, 4)$，是地图中唯一的数字 $3$ 所在的地方。

第一步，往下方滑行，但下方是冰块，于是就直接停留在原地，获得 $3$ 分，并且此位置的数字变为 $0$。

第二步，往下方滑行，但下方仍是冰块，所以还是停留在原地，但这次只获得 $0$ 分，因为所在位置数字已变为 $0$。

第三步往右滑行，滑到座标 $(2, 6)$ 的位置停下，获得 $5$ 分，并且此位置的数字变为 $0$。

第四步往上滑行，但上方是墙壁，于是直接停留在原地，且现在的位置上数字是 $0$，故获得 $0$ 分。

第五步往左滑行，滑到座标 $(2, 2)$ 的位置停下，获得 $1$ 分，并且此位置的数字变为 $0$。

五步共获得的分数为 $3 + 0 + 5 + 0 + 1 = 9$，故此样例的答案为 $9$。

样例输入2

7
#######
#12345#
#4**12#
#67*27#
#*08*1#
#11129#
#######
5 4
5
LBUBU

样例输出2

9

样例2解释

游戏角色的起始位置是座标 $(5, 4)$，是地图中唯一的数字 $8$ 所在的地方。

第一步，往左方滑行，会滑到座标 $(5 ,3)$ 的位置停下，获得 $0$ 分，此位置的数字维持$0$不变。

第二步，敲碎上一步挡住游戏角色的冰块，于是座标 $(5, 2)$ 变为数字$0$的格子。

第三步往上滑行，滑到座标 $(4, 3)$ 的位置停下，获得 $7$ 分，并且此位置的数字变为$0$。

第四步，敲碎上一步挡住游戏角色的冰块，于是座标 $(3, 3)$ 变为数字$0$的格子。

第五步往上滑行，滑到座标 $(2, 3)$ 的位置停下，获得 $2$ 分，并且此位置的数字变为$0$。

五步共获得的分数为 $0 + 7 + 2 = 9$，故此样例的答案为 $9$。