Геномика крупного рогатого скота (Золото)
У Фермера Джона 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 строк описывают геномы коров без пятен. Никакая пятнистая корова на имеет точно такой же геном, как корова без пятен.
Выходные данные
Выведите длину кратчайшей последовательности позиций, достаточной для объяснения пятнистости. Последовательность позиций объясняет пятнистость, если по ней можно предсказывать абсолютно точно пятнистая или нет любая из коров ФД.