Giải bài trực tuyến

English

Vietnamese

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/mkokos

Một tập có N từ, mỗi từ có độ dài 2K kí tự.
Đồ thị có hướng với mỗi đỉnh chứa 1 kí từ được gọi là "kokos" nếu, với mỗi từ trong tập, có 1 đường đi mà nhãn các định của đường đi này tạo thành từ đó. Ngoài ra, mọi đỉnh trên đường đi này phải thỏa mãn:

·  Bậc vào của đỉnh đầu tiên là 0.
·  Bậc vào của K-1 đỉnh tiếp theo là 1.
·  Bậc ra của K-1 đỉnh tiếp theo là 1.
·  Bậc ra của đỉnh cuối cùng là 0.

Nghĩa là các đường đi này chỉ có thể phân nhánh theo K kí tự đầu tiên và gặp nhau ở K kí tự cuối cùng. Một "kokos" là cực tiểu nếu số đỉnh của nó là nhỏ nhất có thể.

Cần xác định số đỉnh này.
 
Ví dụ về kokos cực tiểu (tập các từ của ví dụ thứ 3):

Một cách biểu diễn khác như sau:

Tuy nhiên, nó không là kokos vì các đường đi gặp nhau ở kí tự thứ 4 (D), và rẽ nhanh ở kí tự thứ 6 (E).

Input

Dòng đầu gồm 2 số nguyên N và K, 1 ≤ N ≤ 10 000, 1 ≤ K ≤ 100.
N dòng tiếp theo mỗi dòng chứa một từ, chỉ gồm chữ in hoa tiếng Anh, ('A'-'Z').

Output

Số đỉnh trong kokos cực tiểu.

Sample

input 
 
2 4 
ABCDEFGH 
EFGHIJKL 
 
output 
 
16

input 
 
4 3 
XXZZXX 
XXYYZZ 
AABBCZ 
ABCZZZ 
 
output 
 
18

input 
 
4 4 
ABCDEFGH 
ACBDEFGH 
ABDCFEHG 
EFEFFEGH 
 
output 
 
23