Bessie đang chơi một trò chơi điện tử! Trong trò chơi, ba chữ cái A, B và C là những nút bấm hợp lệ duy nhất. Bessie có thể nhấn các nút theo bất kỳ thứ tự nào mình muốn; tuy nhiên, chỉ có \(N\) combo phân biệt có thể xuất hiện (\(1 \le N \le 20\)). Combo thứ \(i\) được biểu diễn bởi một chuỗi \(S_i\) có độ dài từ 1 đến 15 và chỉ chứa các chữ cái A, B, C.

Mỗi khi Bessie nhấn một dãy chữ cái khớp với một combo, cô nhận được một điểm cho combo đó. Các combo có thể chồng lấn nhau hoặc thậm chí kết thúc cùng lúc! Ví dụ, nếu \(N=3\) và ba combo là ABA, CB, ABACB, khi Bessie nhấn ABACB, cô sẽ có 3 điểm. Bessie có thể ghi điểm từ cùng một combo nhiều lần.

Dĩ nhiên Bessie muốn kiếm điểm nhanh nhất có thể. Nếu cô nhấn chính xác \(K\) nút (\(1 \le K \le 1\,000\)), số điểm tối đa cô có thể kiếm được là bao nhiêu?

Dữ liệu vào

• Dòng 1 chứa hai số nguyên \(N\) và \(K\), cách nhau bởi dấu cách.
• Các dòng từ 2 đến \(N+1\): dòng \(i+1\) chỉ chứa chuỗi \(S_i\), biểu diễn combo thứ \(i\).

Dữ liệu ra

In một số nguyên duy nhất là số điểm tối đa Bessie có thể đạt được.

Ví dụ

3 7
ABA
CB
ABACB

4

Nguồn

USACO 2012 January Contest, Gold - Video Game: https://usaco.org/index.php?page=viewproblem2&cpid=109

Tác giả: Neal Wu, 2012.