Farmer John sở hữu \(N\) con bò có đốm và \(N\) con bò không có đốm. Vừa hoàn thành một khóa học về di truyền học ở bò, ông tin rằng các đốm trên bò của mình là do những đột biến trong hệ gen của bò.

Farmer John phải bỏ ra một khoản chi phí rất lớn để giải trình tự hệ gen của đàn bò. Mỗi hệ gen là một chuỗi độ dài \(M\) được tạo bởi bốn ký tự A, C, G và T. Khi căn chỉnh hệ gen của các con bò, ông thu được một bảng như sau, minh họa với \(N=3\) và \(M=8\):

Vị trí:         1 2 3 4 5 6 7 8

Bò đốm 1:       A A T C C C A T
Bò đốm 2:       A C T T G C A A
Bò đốm 3:       G G T C G C A A

Bò không đốm 1: A C T C C C A G
Bò không đốm 2: A C T C G C A T
Bò không đốm 3: A C T T C C A T

Quan sát kỹ bảng này, ông phỏng đoán rằng đoạn trình tự từ vị trí \(2\) đến vị trí \(5\) đủ để giải thích đặc điểm có đốm. Nghĩa là chỉ cần nhìn vào các ký tự tại những vị trí này (tức các vị trí \(2 \ldots 5\)), Farmer John có thể dự đoán con bò nào có đốm và con bò nào không có đốm. Chẳng hạn, nếu thấy các ký tự GTCG tại những vị trí này, ông biết con bò chắc chắn có đốm.

Hãy giúp FJ tìm độ dài của đoạn vị trí liên tiếp ngắn nhất có thể giải thích đặc điểm có đốm.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) (\(1 \leq N \leq 500\)) và \(M\) (\(3 \leq M \leq 500\)). \(N\) dòng tiếp theo, mỗi dòng chứa một chuỗi gồm \(M\) ký tự, mô tả hệ gen của các con bò đốm. \(N\) dòng cuối mô tả hệ gen của các con bò không đốm. Không có con bò đốm nào có hệ gen hoàn toàn giống một con bò không đốm.

Dữ liệu ra

In độ dài của đoạn vị trí liên tiếp ngắn nhất đủ để giải thích đặc điểm có đốm. Một đoạn vị trí giải thích được đặc điểm có đốm nếu chỉ bằng cách quan sát các vị trí đó trong hệ gen, ta có thể dự đoán hoàn toàn chính xác đặc điểm có đốm trong quần thể bò của Farmer John.

Ví dụ

3 8
AATCCCAT
ACTTGCAA
GGTCGCAA
ACTCCCAG
ACTCGCAT
ACTTCCAT

4

Nguồn

USACO 2017 US Open Contest, Gold — Bovine Genomics. Tác giả đề: Brian Dean.

https://usaco.org/index.php?page=viewproblem2&cpid=741