MKOKOS - KOKOS

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

 


Được gửi lên bởi:psetter
Ngày:2009-06-06
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:COI 06

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.