Радио контакт
Фермер Джон потерял колокольчик и Беси согласилась ему помочь в поисках. Они двигаются по своим маршрутам, но стараются общаться по радиосвязи. При этом они хотят использовать как можно меньше энергии своих радиоустройств.
Фермер Джон начинает в позиции (f[x], f[y]) и планирует сделать n шагов, каждый из которых в одном из 4 направлений: 'N' (север), 'E' (восток), 'S' (юг), 'W' запад. Беси начинает в позиции (b[x], b[y]) и делает аналогичные m шагов. Эти пути могут иметь общие точки. В каждый момент времени ФД может остаться в своей текущей позиции либо сделать один шаг вперёд по своему маршруту (если ещё не достиг финальной позиции). В каждый момент времени (исключая тот момент, когда они находятся в стартовой позиции), энергия, потреблённая их радиоустройствами равна квадрату расстояния между ними.
Помогите ФД и Беси спланировать совместное движение так, чтобы минимизировать общее количество потреблённой энергии, включая финальный шаг, когда оба достигнут финальной позиции.
Входные данные
Первая строка содержит n и m (1 ≤ n, m ≤ 1000). Вторая строка содержит целые числа f[x] и f[y], третья строка содержит b[x] и b[y] (0 ≤ f[x], f[y], b[x], b[y] ≤ 1000). Следующая строка содержит строку длины n, описывающая путь ФД, и последняя строка содержит строку длины m, описывающая путь Беси.
Гарантируется, что координаты ФД и Беси всегда в интервале (0 ≤ x, y ≤ 1000) на протяжении всего маршрута. Заметим, что Восток - это положительное направление по оси Х, а Север - положительное направление по оси Y.
Выходные данные
Выведите одно целое число, указывающее минимальное количество энергии, которое ФД и Беси могут использовать во время своего путешествия.