C. Helicopter
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Компании VK понадобилось срочно переместить сервера из одного дата-центра в другой. Это очень важная и срочная задача, потому что во время их перемещения не все сервисы будут полноценно функционировать, однако на дорогах сегодня почему-то пробки, поэтому сервера будут перемещаться на вертолете.

Карта области, над которой может перемещаться вертолет, представляет из себя поле, состоящее из $$$n$$$ строк и $$$m$$$ столбцов. Нумерация строк идет от $$$1$$$ до $$$n$$$ сверху-вниз, нумерация столбцов от $$$1$$$ до $$$m$$$ слева-направо. Каждая клетка представляет из себя участок одинаковой высоты. Будем характеризовать клетку в строке $$$i$$$ и столбце $$$j$$$ как $$$(i, j)$$$, а минимальную высоту, на которой может безопасно находиться вертолет на соответствующем участке, как $$$a_{i, j}$$$.

Сервера надо переместить из клетки $$$(1, 1)$$$ в клетку $$$(n, m)$$$. Будем считать, что вертолет уже поднялся в воздух, и находится на высоте $$$a_{1, 1}$$$. При попадании вертолета в клетку $$$(n, m)$$$ на любой разрешенной высоте маршрут считается завершенным.

В любой момент времени высота, на которой находится вертолет, должна быть не меньше минимальной высоты полета для текущей клетки, то есть если обозначить за $$$h$$$ высоту, на которой сейчас находится вертолет в клетке $$$(i, j)$$$, должно выполняться $$$a_{i, j} \le h$$$. При этом из позиции $$$(i, j)$$$ на высоте $$$h$$$ можно:

  • Перелететь в соседнюю по стороне клетку, потратив на такой перелет $$$h$$$ топлива. При этом высота не изменится, а такое перемещение можно сделать только если $$$a$$$ клетки, в которую совершается перелет, не больше $$$h$$$.
  • Увеличить свою высоту на произвольное $$$x \ge 0$$$. На такой подъем тратится $$$x$$$ топлива.
  • Опуститься на любую высоту не меньше $$$a_{i,j}$$$. На это топливо не тратится.

Из-за погодных условий вертолет не всегда может лететь во все стороны. Доступные направления задаются строкой $$$\mathtt{s}$$$. Каждое возможное направление полета задается следующими буквами:

  • 'R' — разрешено движение вправо из клетки $$$(i, j)$$$ в клетку $$$(i, j + 1)$$$.
  • 'L' — разрешено движение влево из клетки $$$(i, j)$$$ в клетку $$$(i, j - 1)$$$.
  • 'U' — разрешено движение вверх из клетки $$$(i, j)$$$ в клетку $$$(i - 1, j)$$$.
  • 'D' — разрешено движение вниз из клетки $$$(i, j)$$$ в клетку $$$(i + 1, j)$$$.

Увеличивать и уменьшать высоту можно всегда. Направления перемещения 'R' и 'D' всегда разрешены. Перемещаться за границу поля, разумеется, нельзя.

Программисты из VK быстро справились определить оптимальный по затратам топлива маршрут для вертолета, даже при таком большом количестве условий на его перемещения. А справитесь ли вы?

Входные данные

В первой строке даны два целых числа $$$n$$$ и $$$m$$$ — размеры поля, над которым перемещается вертолет ($$$1 \le n, m \le 1000$$$).

Во второй строке дана строка $$$\mathtt{s}$$$, состоящая из различных символов 'L', 'R', 'U' и 'D' — разрешенные направления полета ($$$2 \le |s| \le 4$$$). Гарантируется, что $$$\text{'\t{R}'}, \text{'\t{D}'} \in \mathtt{s}$$$.

Далее идут $$$n$$$ строк по $$$m$$$ чисел — описание поля, $$$i$$$-я строка содержит числа $$$a_{i,j}$$$ (значения минимальной высоты полета), описывающие $$$i$$$-ю строку поля ($$$0 \le a_{i, j} \le 10^9$$$).

Выходные данные

Выведите единственное число — минимальное количество топлива, чтобы добраться из положения на высоте $$$a_{1,1}$$$ в клетке $$$(1, 1)$$$ до клетки $$$(n, m)$$$.

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены. Далее за $$$A$$$ обозначено $$$\max\limits_{i,j} a_{i,j}$$$.

ПодзадачаБаллыОграничения Необходимые подзадачи Информация о проверке
0–примеры из условияполная
15$$$n, m, A \le 10$$$0полная
25$$$n, m \le 10^3$$$, $$$A \le 1$$$первая ошибка
35$$$n = 1$$$, $$$m \le 10^3$$$первая ошибка
47$$$n, m, A \le 500$$$, $$$\mathtt{s} = \text{«\t{RD}»}$$$первая ошибка
515$$$n, m \le 10^3$$$, $$$\mathtt{s} = \text{«\t{RD}»}$$$4первая ошибка
65$$$n, m \le 10^3$$$, и $$$a_{i - 1, j}, a_{i, j - 1} \le a_{i, j}$$$первая ошибка
715$$$n, m \le 10^3$$$, $$$\mathtt{s} = \text{«\t{LRD}»}$$$5первая ошибка
85$$$n, m, A \le 100$$$0, 1первая ошибка
913$$$n, m, A \le 500$$$0, 1, 4, 8первая ошибка
1025без дополнительных ограничений0 – 9первая ошибка
Примеры
Входные данные
3 3
LRDU
1 2 4
4 4 4
1 1 1
Выходные данные
13
Входные данные
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
Выходные данные
30
Примечание

В первом примере выгодно лететь вниз до упора, затем вправо до упора. Первые два перелета придется совершить на высоте $$$4$$$, последние два можно совершить на высоте $$$1$$$.

Во втором примере оптимальный путь проходит по клеткам с $$$a_{i,j} = 0$$$ и стоит $$$0$$$ топлива, однако для этого надо перемещаться вверх, а перемещения вверх запрещены. В таком случае можно пролететь по «нулевым» клеткам через клетку $$$(1, 2)$$$ или $$$(2, 4)$$$ с $$$a_{1,2} = a_{2,4} = 10$$$. Для перелета через любую из них понадобится подняться на высоту $$$10$$$, после совершить два перелета на этой высоте.