Симулятор студента
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В коворкинге Университета ИТМО решили установить приставку, чтобы студенты могли интересно проводить перерывы между парами. Правда пока что на этой приставке доступна только одна игра — «Симулятор студента».

Как и все симуляторы, эта игра бесконечно реалистичная, поэтому в ней можно делать все, что делают студенты — в том числе, опаздывать на пары. Поле в событии «Успеть на пару» представляет собой бесконечную клетчатую решетку. Главный герой игры Гриша торопится из общежития в клетке с координатами $$$(0, 0)$$$ в ИТМО с координатами $$$(x, y)$$$.

Для управления персонажем нужно использовать кнопки на джойстике. Можно переместиться на одну клетку вправо ($$$+1$$$ по координате $$$X$$$), нажав «R», влево ($$$-1$$$ по координате $$$X$$$), нажав «L», вверх ($$$+1$$$ по координате $$$Y$$$), нажав «U» и вниз ($$$-1$$$ по координате $$$Y$$$), нажав «D».

Помимо этого, игрок может нажать специальный код $$$S$$$. Если игрок нажал все клавиши кода подряд, а после этого нажал на кнопку «Q», то происходит $$$d$$$ перемещений в какую-то из соседних клеток. Клетки называются соседними, если у них есть общая сторона. Например, если код равен «LRUU», то после нажатия комбинации «LRUUQ», Гриша переместится влево, вправо, и дважды вверх, после чего сделает еще $$$d$$$ перемещений.

Ваша задача — привести Гришу в ИТМО за минимальное число нажатий кнопок. Гриша по природе очень удачливый, а еще он совсем критично опаздывает, поэтому схватится за любой шанс успеть. Иными словами, можно считать, что $$$d$$$ перемещений после нажатия кода всегда двигают Гришу так, чтобы минимизировать количество оставшихся после этого нажатий на кнопки. Определите, какое число нажатий на кнопки понадобится.

Заметьте, что достаточно провести Гришу через клетку $$$(x, y)$$$ — как только он окажется в ней, он зайдет в ИТМО и больше не будет перемещаться. Например, если код «UQ» вызывает $$$d = 10$$$ перемещений, а требуется попасть в клетку $$$(3, 0)$$$, то ответ на задачу равен $$$2$$$ — достаточно прожать код один раз, чтобы Гришин путь прошел через ИТМО.

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

В первой строке через пробел даны три числа $$$x$$$, $$$y$$$ и $$$d$$$ — координаты конечной клетки и количество перемещений, совершаемых при нажатии кода ($$$1 \le x, y, d \le 10^9$$$).

Во второй строке вводится сам код $$$S$$$ ($$$1 \le |S| \le 2 \cdot 10^5$$$). Код состоит из символов 'R', 'L', 'U' и 'D'.

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

Выведите единственное число — длину кратчайшей последовательности нажатий на кнопки, приводящей Гришу в ИТМО.

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

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.

ПодзадачаБаллы Дополнительные ограничения Необходимые подзадачи Информация о проверке
112$$$x, y, d, |S| \le 10$$$полная
219$$$x, y, d \le 100$$$; $$$|S| \le 10$$$1полная
322$$$x, y \le 10^6$$$1, 2первая ошибка
417$$$|S| = 1$$$первая ошибка
530нет1 — 4первая ошибка

Примеры

Входные данные
3 5 6
RDR
Выходные данные
5
Входные данные
8 6 9
RLRLUDLLRU
Выходные данные
14
Входные данные
4 1 10
R
Выходные данные
2
Входные данные
3 5 3
LURL
Выходные данные
8
Входные данные
4 5 3
UDU
Выходные данные
9
Входные данные
5 5 9
RLDRU
Выходные данные
6
Входные данные
3 5 3
RR
Выходные данные
6