Затоптаний кабель
Нейтан О. Девіс керує компанією, яка володіє веб-сервісом з великою кількістю користувачів. Через це його офіс переповнений серверами, маршрутизаторами та заплутаними кабелями локальної мережі.
Наразі він дуже стурбований заплутаними кабелями, оскільки вони викликають багато проблем. Наприклад, співробітники часто спотикаються об кабелі. Якщо кабель від'єднано, це не завдає шкоди, але якщо підключено, комп'ютери можуть вийти з ладу. Він планує встановити новий комп'ютер і кабель, і хоче зменшити кількість разів, коли співробітники переступають через новий кабель.
Його офіс розташований у двовимірній сітці розміром H×W клітинок. Новий кабель повинен проходити вздовж країв клітинок, а його кінці знаходяться в кутах клітинок. Сітка має координати з нульовим початком, де верхній лівий кут — це (0, 0).
Кожен співробітник починає роботу з певної клітинки і пересувається по офісу за фіксованим повторюваним шаблоном кожного дня. Шаблон описується рядком з чотирьох символів: U, D, L і R. U означає рух вгору, D — вниз, R — вправо, а L — вліво. Наприклад, UULLDDRR означає рух вгору, вгору, вліво, вліво, вниз, вниз, вправо, вправо. Співробітник повторює цей шаблон фіксовану кількість разів T. Якщо співробітник виходить за межі сітки, він залишається в поточній клітинці.
Вам надано рухові шаблони всіх співробітників і позиції обох кінців нового кабелю. Ваше завдання — знайти оптимальне розташування нового кабелю, яке мінімізує загальну кількість разів, коли співробітники переступають через кабель.
Вхідні дані
Перший рядок вхідних даних містить три цілі числа: розміри офісу W, H (1 ≤ W, H ≤ 500) та кількість співробітників N (1 ≤ N ≤ 1000). Наступний рядок містить дві пари x−y (0 ≤ x ≤ W, 0 ≤ y ≤ H), які вказують на позиції двох кінців LAN кабелю. Ці значення представляють координати клітинок, до яких підключено кабель у верхньому лівому куті. Винятково, x=W означає правий край крайньої правої клітинки, а y=H — нижній край крайньої нижньої клітинки.
Наступні рядки описують початкові позиції співробітників і їхні рухові шаблони. Перший рядок містить пару x-y (0 ≤ x < W, 0 ≤ y < H), яка вказує на початкову клітинку співробітника. Наступний рядок містить ціле число T (1 ≤ T ≤ 100) і рядок, що складається з символів U, D, L і R. Довжина рядка шаблону від 1 до 1000. Ці два рядки повторюються N разів.
Вихідні дані
Виведіть мінімальну кількість разів, коли співробітники переступатимуть через кабель в одному рядку.