Gen bò (Gold)

Một trang trại có $N$ con bò đốm và $N$ con bò trơn. Bộ gen của mỗi con bò được mô tả bằng một chuỗi độ dài $M$ gồm các ký tự A, C, G, T; vị trí thứ $j$ của mọi chuỗi tương ứng với cùng một vị trí trên bộ gen.

Người ta muốn tìm một đoạn vị trí liên tiếp $[l,r]$ đủ để phân biệt hoàn toàn hai đàn: nếu chỉ đọc các ký tự từ vị trí $l$ đến vị trí $r$ thì không có con bò đốm nào cho ra chuỗi giống hệt chuỗi của một con bò trơn nào.

Hãy tìm độ dài $r-l+1$ nhỏ nhất của một đoạn như vậy.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $N$ và $M$.
• $N$ dòng tiếp theo, mỗi dòng là bộ gen của một con bò đốm.
• $N$ dòng cuối, mỗi dòng là bộ gen của một con bò trơn.

Dữ liệu ra

Một số nguyên duy nhất: độ dài nhỏ nhất của đoạn liên tiếp phân biệt được hai đàn.

Ràng buộc

• $1\le N\le 500$, $1\le M\le 500$
• Mỗi bộ gen gồm đúng $M$ ký tự thuộc tập $\{$A, C, G, T$\}$
• Hai con bò khác nhau có thể có bộ gen giống nhau, nhưng dữ liệu đảm bảo không có con bò đốm nào có bộ gen trùng hoàn toàn với một con bò trơn nào. Do đó đoạn $[1,M]$ luôn là một đáp án hợp lệ.

Ví dụ