# Travelling Salesman Problem

Time Limit: 3000/1500 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

## Description

Teacher Mai is in a maze with $n$ rows and $m$ columns. There is a non-negative number in each cell. Teacher Mai wants to walk from the top left corner $(1,1)$ to the bottom right corner $(n,m)$. He can choose one direction and walk to this adjacent cell. However, he can't go out of the maze, and he can't visit a cell more than once.

Teacher Mai wants to maximize the sum of numbers in his path. And you need to print this path.

## Input

There are multiple test cases.

For each test case, the first line contains two numbers $n,m(1\leq n,m\leq 100,n*m\geq 2)$.

In following $n$ lines, each line contains $m$ numbers. The $j$-th number in the $i$-th line means the number in the cell $(i,j)$. Every number in the cell is not more than $10^4$.

## Output

For each test case, in the first line, you should print the maximum sum.

In the next line you should print a string consisting of "L","R","U" and "D", which represents the path you find. If you are in the cell $(x,y)$, "L" means you walk to cell $(x,y-1)$, "R" means you walk to cell $(x,y+1)$, "U" means you walk to cell $(x-1,y)$, "D" means you walk to cell $(x+1,y)$.

## Sample Input

3 3
2 3 3
3 3 3
3 3 2

## Sample Output

25
RRDLLDRR

wange2014

## Source

2015 Multi-University Training Contest 9