Радіо контакт
Фермер Джон загубив дзвіночок, і Бессі погодилася допомогти йому в пошуках. Вони рухаються своїми маршрутами, але намагаються підтримувати зв'язок за допомогою радіо. При цьому вони прагнуть використовувати якомога менше енергії своїх радіопристроїв.
Фермер Джон починає з позиції (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) протягом усього маршруту. Зазначимо, що схід - це позитивний напрямок по осі X, а північ - позитивний напрямок по осі Y.
Вихідні дані
Виведіть одне ціле число, яке вказує мінімальну кількість енергії, яку Фермер Джон і Бессі можуть використати під час своєї подорожі.