Геноміка великої рогатої худоби (Золото)
У фермера Джона є n корів з плямами та n корів без плям. Після вивчення генетики, Джон переконаний, що плями у корів викликані генетичними мутаціями.
Фермер Джон витратив значні кошти, щоб отримати геноми своїх корів. Кожен геном представлений рядком довжиною m, що складається з символів A, C, G, T. Після запису всіх геномів, він отримав таку таблицю, де n = 3 і m = 8:
Позиція : 1 2 3 4 5 6 7 8 Плямиста корова 1: A A T C C C A T Плямиста корова 2: A C T T G C A A Плямиста корова 3: G G T C G C A A Корова без плям 1: A C T C C C A G Корова без плям 2: A C T C G C A T Корова без плям 3: A C T T C C A T
Ретельно вивчивши цю таблицю, він виявив, що послідовність від позиції 2 до позиції 5 може пояснити плямистість. Тобто, аналізуючи символи в цих позиціях (2 .. 5), Джон може визначити, які з його корів плямисті, а які ні. Наприклад, якщо в цих позиціях з'являються символи GTCG, він знає, що корова буде плямиста.
Допоможіть Джону знайти довжину найкоротшої послідовності позицій, яка може пояснити плямистість.
Вхідні дані
Перший рядок містить n (1 ≤ n ≤ 500) і m (3 ≤ m ≤ 500). Кожен з наступних n рядків містить по m символів, що описують геноми плямистих корів. Наступні n рядків описують геноми корів без плям. Жодна плямиста корова не має точно такого ж геному, як корова без плям.
Вихідні дані
Виведіть довжину найкоротшої послідовності позицій, яка достатня для пояснення плямистості. Послідовність позицій пояснює плямистість, якщо за нею можна точно передбачити, чи є корова плямистою.