P6550 [COCI 2010/2011 #2] LUNAPARK

Mirko 对所有书籍都感到了厌倦，因此尽管他不喜欢玩过山车，他还是决定和朋友一起去游乐园。 当他的朋友们度过美好的时光时，Mirko 则坐在长椅上，等待着并思考过山车的可能路线。 游乐园可以用 $r$ 行 $c$ 列的表格来表示。 过山车必须从表格的左上角开始，到表格的右下角结束。 每个单元格最多可以访问一次，但并非所有单元格都需要访问。 它可以继续从当前单元格到其上方，下方，左侧或右侧的相邻单元的路径。 每个单元格都有一个与之相关的正整数值，表示该单元格可以为游客增加的娱乐程度。过山车的总娱乐程度是过山车所访问的所有单元格的娱乐程度的总和。 帮助 Mirko 确定最有趣（总娱乐程度最大）的过山车路线之一。

第一行两个整数 $r$ 和 $c$，具体含义请见题目描述。 接下来 $r$ 行，每行 $c$ 个整数（用空格隔开），表示相对应的单元格可以为游客增加的娱乐程度。

一行一个大写字符串，由 `U`、`D`、`L`、`R` 组成（`U` 表示过山车接下来向上走，`D` 表示向下走，`L` 表示向左走，`R` 表示向右走），表示过山车为获得最大娱乐程度应该走的路线。

#### 数据规模与约定 - 对于 $70\%$ 的数据，保证 $2 \leq r,c \leq 30$。 - 对于 $100\%$ 的数据，保证 $2 \leq r,c \leq 1 \times 10^3$，输出字符串的每一位只可能是 `U`、`D`、`L`、`R`。 #### 说明 - 本题满分 $120$ 分。 - 题目译自 [COCI2010-2011](https://hsin.hr/coci/archive/2010_2011/) [CONTEST #2](https://hsin.hr/coci/archive/2010_2011/contest2_tasks.pdf) LUNAPARK，译者 @[mnesia](https://www.luogu.com.cn/user/115711)。 #### 鸣谢 感谢 @[Silence_water](https://www.luogu.com.cn/user/338630) 提供的 Special Judge。 #### 提示 输出结果可能不唯一。