Лицарський матчевий поєдинок#3787
Є дві команди лицарів, у кожній з яких відповідно та лицарів. Лицарі в кожній команді пронумеровані від до та від до . Вони опинилися в головоломці на сітці розміром W \times H. Головоломка має лише чотири виходи, розташовані в чотирьох кутах. Лицар може рухатися лише вгору, вниз, вліво або вправо, і час переміщення між сусідніми клітинками є фіксованим. Лицарі можуть утворити "бойову пару", якщо виконуються такі умови:
Лицарі з різних команд.
Обидва можуть дістатися одного з виходів.
Найменший час, необхідний для досягнення одного з виходів, однаковий.
Скільки "бойових пар" вони можуть утворити?
Для цього лідер дає такі вказівки:
Кожна команда перенумеровує лицарів за найменшим часом, необхідним для виходу з головоломки. Той, хто витрачає найменший час, отримує ID , а той, хто витрачає найбільший час, отримує ID або . Якщо кілька лицарів витрачають однаковий час, то той, у кого оригінальний ID нижчий, отримує нижчий ID.
Обрані лицарі з однієї команди повинні мати послідовні ID.
Формувати "бойові пари" відповідно до ID по черзі. Тобто той, хто має найнижчий ID, повинен утворити пару з тим, хто має найнижчий ID в іншій команді, і так далі.
Є декілька тестових випадків. Вхід кожного тестового випадку описаний нижче.
Перший рядок містить чотири цілі числа , , , (0 < N, M < 300, 10 < W, H < 50).
Далі йдуть рядків, кожен з яких містить символів, що описують головоломку. Символ '.' означає, що клітинка порожня, і в ній може бути нескінченна кількість лицарів. Символ '#' позначає бар'єр, на який жоден лицар не може ступити. Чотири кути є порожніми.
Далі йдуть N+M рядків, кожен з яких містить пару цілих чисел (, ) (0 \le x < H, 0 \le y < W), що вказують на початкове розташування лицаря в -му рядку та -му стовпці.
Вхід закінчується кінцем файлу.
Виведіть ціле число, що вказує на максимальну кількість "бойових пар", які вони можуть утворити.
Приклад 1