Радіозв'язок#10599
Фермер Джон загубив свій улюблений дзвіночок для корови, і корова Бессі погодилася допомогти йому знайти його! Вони розходяться і шукають ферму різними шляхами, але залишаються на зв'язку по рації, щоб мати можливість спілкуватися одне з одним. На жаль, батарейки в їхніх раціях розряджаються, тому вони хочуть спланувати свої переміщення так, щоб економити енергію, намагаючись знаходитися якомога ближче одне до одного.
Фермер Джон починає з точки (f_x, f_y) і планує пройти шлях, що складається з кроків, кожен з яких — це '' (північ), '' (схід), '' (південь) або '' (захід). Бессі починає з точки (b_x, b_y) і йде схожим шляхом, що складається з кроків. Два шляхи можуть мати спільні точки. На кожному кроці за часом Фермер Джон може або залишитися на своєму поточному місці, або зробити один крок вперед по своєму шляху, у тому напрямку, який іде наступним (за умови, що він ще не досяг кінця свого шляху). Бессі може зробити такий самий вибір.
На кожному кроці за часом, окрім початкового моменту, коли вони перебувають у своїх стартових точках, їхні рації споживають кількість енергії, що дорівнює квадрату відстані між ними.
Будь ласка, допоможіть ФД та Бессі спланувати спільну стратегію переміщення, яка мінімізує загальну кількість спожитої енергії аж до моменту, коли вони вперше досягнуть кінцевих точок своїх відповідних шляхів включно.
Перший рядок містить два цілих числа та m~(1 \le n, m \le 1000). Другий рядок містить два цілих числа f_x та f_y, а третій рядок містить два цілих числа b_x та b_y~(0 \le f_x, f_y, b_x, b_y \le 1000). Наступний рядок містить рядок довжини , що описує шлях ФД, а останній рядок містить рядок довжини , що описує шлях Бессі.
Гарантується, що координати Фермера Джона та Бессі завжди залишаються в межах 0 \le x, y \le 1000 протягом усієї подорожі. Зауважте, що схід відповідає додатному напрямку , тоді як північ відповідає додатному напрямку .
Виведіть мінімальну кількість енергії, яку можуть спожити ФД та Бессі під час своєї подорожі.
Приклад 1