Ít người biết rằng bò rất thích các câu đố, đặc biệt là câu đố chữ. Gần đây, những con bò của Nông dân John đã tạo ra một trò chơi "tìm từ" thú vị. Dưới đây là một ví dụ về trò chơi như vậy:

USOPEN
OOMABO
MOOMXO
PQMROM

Vì là bò nên từ duy nhất chúng quan tâm là MOO. Từ này có thể xuất hiện ở nhiều vị trí trong bảng tìm từ, theo chiều ngang, chiều dọc hoặc đường chéo. Ví dụ trên chứa 6 từ MOO.

Nông dân John cũng là một người hâm mộ các câu đố chữ. Vì đàn bò không muốn ông giải bảng tìm từ trước khi chúng có cơ hội tự thử sức, chúng đã mã hóa nội dung bảng bằng một "mật mã thay thế", trong đó mỗi chữ cái trong bảng chữ cái được thay bằng một chữ cái khác. Chẳng hạn, A có thể được ánh xạ thành X, B có thể được ánh xạ thành A, v.v. Không chữ cái nào được ánh xạ thành chính nó, và không có hai chữ cái nào được ánh xạ thành cùng một chữ cái (vì nếu không, việc giải mã sẽ nhập nhằng).

Thật không may, đàn bò đã làm thất lạc mật mã thay thế cần thiết để giải mã bảng. Hãy giúp chúng xác định số lượng từ MOO lớn nhất có thể tồn tại trong bảng với một lựa chọn mật mã thay thế phù hợp.

Dữ liệu vào

Tệp moocrypt.in:

Dòng đầu tiên chứa \(N\) và \(M\), lần lượt là số hàng và số cột của bảng (cả hai đều không quá 50). Mỗi dòng trong \(N\) dòng tiếp theo chứa \(M\) ký tự, mô tả một hàng của bảng đã mã hóa. Mỗi ký tự là một chữ cái tiếng Anh viết hoa trong khoảng A đến Z.

Dữ liệu ra

Tệp moocrypt.out:

In số lượng từ MOO lớn nhất có thể có trong bảng nếu bảng được giải mã bằng một mật mã thay thế phù hợp.

Ví dụ

4 6
TAMHGI
MMQVWM
QMMQSM
HBQUMQ

6

Nguồn

USACO 2015 US Open, Bronze — Moocryption

Tác giả bài: Brian Dean, 2015.