Фермер Джон потерял колокольчик и Беси согласилась ему помочь в поисках.
Они двигаются по своим маршрутам, но стараются общаться по радиосвязи.
При этом они хотят использовать как можно меньше энергии своих
радиоустройств.
Фермер Джон начинает в позиции (\(f_x, f_y\)) и планирует сделать \(N\)
шагов, каждый из которых в одном из 4 направлений: 'N' (север),
'E' (восток), 'S'(юг), 'W' запад.
Беси начинает в позиции (\(b_x, b_y\)) и делает аналогичные \(M\) шагов.
Эти пути могут иметь общие точки. В каждый момент времени ФД может
остаться в своей текущей позиции либо сделать один шаг вперёд по своему
маршруту (если ещё не достиг финальной позиции). В каждый момент времени
(исключая тот момент, когда они находятся в стартовой позиции), энергия,
потреблённая их радиоустройствами равна квадрату расстояния между ними.
Помогите ФД и Беси спланировать совместное движение так, чтобы минимизировать
общее количество потреблённой энергии, включая финальный шаг, когда оба достигнут
финальной позиции.
ФОРМАТ ВВОДА (файл radio.in):
Первая строка ввода содержит
\(N\) и
\(M\) (
\(1 \leq N, M \leq 1000\)).
Вторая строка содержит целые числа
\(f_x\) и
\(f_y\), третья строка содержит
\(b_x\) и
\(b_y\) (
\(0 \leq f_x, f_y, b_x, b_y \leq 1000\)). Следующая строка
содержит строку длины
\(N\), описывающая путь ФД, и последняя строка содержит
строку длины
\(M\), описывающая путь Беси.
Гарантируется, что координаты ФД и Беси всегда в интервале (\(0 \leq x,y \leq 1000\))
на протяжении всего маршрута. Заметим, что Восток - это положительное направление
по оси Х, а Север - положительное направление по оси Y.
ФОРМАТ ВЫВОДА (файл radio.out):
Выведите одно целое число, указывающее минимальное количество энергии,
которое ФД и Беси могут использовать во время своего путешествия.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 7
3 0
5 0
NN
NWWWWWN
|
28
|