C. Helicopter
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

The VK company urgently needed to move servers from one data center to another. This is a very important and urgent task, because not all services will function properly during their movement, but there is traffic on the roads today, so the servers will be moved by helicopter.

The map of the area over which the helicopter can move is a field consisting of $$$n$$$ rows and $$$m$$$ columns. The numbering of the rows goes from $$$1$$$ to $$$n$$$ from top to bottom, the numbering of the columns goes from $$$1$$$ to $$$m$$$ from left to right. Each cell represents a section of the same height. We will characterize the cell in row $$$i$$$ and column $$$j$$$ as $$$(i, j)$$$, and the minimum height at which the helicopter can safely fly in the corresponding section as $$$a_{i, j}$$$.

The servers need to be moved from cell $$$(1, 1)$$$ to cell $$$(n, m)$$$. The helicopter has already taken off and is at a height of $$$a_{1, 1}$$$. When the helicopter reaches cell $$$(n, m)$$$ at any allowed height, the route is considered completed.

At any given time the height at which the helicopter is located must be at least the minimum flight height for the current cell, that is, if we denote the height at which the helicopter is currently located in cell $$$(i, j)$$$ as $$$h$$$, it must satisfy $$$a_{i, j} \le h$$$. At the same time, from position $$$(i, j)$$$ at height $$$h$$$ the helicopter can:

  • Fly to an adjacent cell, spending $$$h$$$ fuel for such a flight. The height will not change, and such a movement can only be made if the value of $$$a$$$ of the cell to which the flight is made is not greater than $$$h$$$.
  • Increase its height by any $$$x \ge 0$$$. This action will consume $$$x$$$ fuel.
  • Descend to any height not less than $$$a_{i,j}$$$. This will not consume fuel.

Due to weather conditions the helicopter may not be able to fly in all directions. The available directions are specified by the string $$$\mathtt{s}$$$. Each possible flight direction is represented by the following letters:

  • 'R' — movement to the right from cell $$$(i, j)$$$ to cell $$$(i, j + 1)$$$ is allowed.
  • 'L' — movement to the left from cell $$$(i, j)$$$ to cell $$$(i, j - 1)$$$ is allowed.
  • 'U' — movement upwards from cell $$$(i, j)$$$ to cell $$$(i - 1, j)$$$ is allowed.
  • 'D' — movement downwards from cell $$$(i, j)$$$ to cell $$$(i + 1, j)$$$ is allowed.

The height can always be increased or decreased. The movement directions 'R' and 'D' are always allowed. It is not possible to move beyond the field boundaries.

Programmers from VK quickly managed to determine the optimal fuel costs for the helicopter's route, even with such a large number of conditions on its movement. Can you do it too?

Input

The first line contains two integers $$$n$$$ and $$$m$$$ — the dimensions of the field over which the helicopter moves ($$$1 \le n, m \le 1000$$$).

The second line contains a string $$$\mathtt{s}$$$, consisting of different characters 'L', 'R', 'U', and 'D' — the allowed flight directions ($$$2 \le |s| \le 4$$$). It is guaranteed that $$$\text{'\t{R}'}, \text{'\t{D}'} \in \mathtt{s}$$$.

Then there are $$$n$$$ lines with $$$m$$$ numbers each — the description of the field; the $$$i$$$-th line contains the numbers $$$a_{i,j}$$$ (the values of the minimum flight height) describing the $$$i$$$-th row of the field ($$$0 \le a_{i, j} \le 10^9$$$).

Output

Output a single number — the minimum amount of fuel needed to travel from the position at height $$$a_{1,1}$$$ in cell $$$(1, 1)$$$ to cell $$$(n, m)$$$.

Scoring

Points for each subtask are awarded only if all the tests of this subtask and the necessary subtasks are successfully passed. Here, $$$A$$$ denotes $$$\max\limits_{i,j} a_{i,j}$$$.

SubtaskPointsConstraints Necessary subtasks Feedback policy
0–examplesfull
15$$$n, m, A \le 10$$$0full
25$$$n, m \le 10^3$$$, $$$A \le 1$$$first error
35$$$n = 1$$$, $$$m \le 10^3$$$first error
47$$$n, m, A \le 500$$$, $$$\mathtt{s} = \text{"\t{RD}"}$$$first error
515$$$n, m \le 10^3$$$, $$$\mathtt{s} = \text{"\t{RD}"}$$$4first error
65$$$n, m \le 10^3$$$, and $$$a_{i - 1, j}, a_{i, j - 1} \le a_{i, j}$$$first error
715$$$n, m \le 10^3$$$, $$$\mathtt{s} = \text{"\t{LRD}"}$$$5first error
85$$$n, m, A \le 100$$$0, 1first error
913$$$n, m, A \le 500$$$0, 1, 4, 8first error
1025no additional constraints0 – 9first error
Examples
Input
3 3
LRDU
1 2 4
4 4 4
1 1 1
Output
13
Input
5 5
LRD
0 10 0 0 0
0 0 0 10 0
10 10 10 10 0
9 5 3 2 0
3 3 2 5 0
Output
30
Note

In the first example the best path is to fly down to the limit, then right to the limit. The first two flights will have to be made at a height of $$$4$$$, the last two can be made at a height of $$$1$$$.

In the second example, the optimal path passes through cells with $$$a_{i,j} = 0$$$ and costs $$$0$$$ fuel, but for this it is necessary to move upwards, and upward movements are prohibited. In this case it is possible to fly over the "zero" cells through cell $$$(1, 2)$$$ or $$$(2, 4)$$$ with $$$a_{1,2} = a_{2,4} = 10$$$. To fly over either of them it will be necessary to ascend to a height of $$$10$$$ then perform two movements at this height.