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ị trí:         1 2 3 4 5 6 7 ... M

Bò đốm 1:       A A T C C C A ... T
Bò đốm 2:       G A 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 G T T G C A ... T
Bò không đốm 3: A G T T C C A ... T

Quan sát kỹ bảng này, ông phỏng đoán rằng các vị trí \(2\) và \(4\) đủ để 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 hai vị trí này, 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 G và C thì con bò chắc chắn có đốm).

Farmer John tin rằng đặc điểm có đốm không thể được giải thích chỉ bằng một hoặc hai vị trí trong hệ gen, mà phải bằng cách quan sát một tập hợp gồm ba vị trí phân biệt. Hãy giúp ông đếm số tập hợp gồm ba vị trí phân biệt mà mỗi tập hợp có thể giải thích được đặ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 50\)). \(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.

Dữ liệu ra

In số tập hợp gồm ba vị trí phân biệt có thể giải thích đặc điểm có đốm. Một tập hợp gồm ba vị trí giải thích được đặc điểm có đốm nếu chỉ bằng cách quan sát ba 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
GATTGCAA
GGTCGCAA
ACTCCCAG
ACTCGCAT
ACTTCCAT

22

Nguồn

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

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