Submit solution

Points: 1.00 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
COI 06
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

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)~:

image

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

image

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 \leq N \leq 10 000~, ~1 \leq K \leq 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 1

2 4 
ABCDEFGH 
EFGHIJKL

Sample Output 1

16

Sample Input 2

4 3 
XXZZXX 
XXYYZZ 
AABBCZ 
ABCZZZ

Sample Output 2

18

Sample Input 3

4 4 
ABCDEFGH 
ACBDEFGH 
ABDCFEHG 
EFEFFEGH

Sample Output 3

23

Comments

Please read the guidelines before commenting.


There are no comments at the moment.