Trong Tin sinh học, các nhà khoa học thường phân tích DNA thông qua những đoạn ngắn có cùng độ dài, gọi là các {~K~-mer}. Một chuỗi DNA là một xâu chỉ gồm bốn ký tự {A}, {C}, {G} và {T}.

Với một chuỗi DNA có độ dài ~L\ge K~, ta thu được ~L-K+1~ đoạn con liên tiếp có độ dài ~K~, bắt đầu lần lượt tại các vị trí ~1,2,\ldots,L-K+1~.

Chẳng hạn, với ~K=3~, chuỗi {ACGTA} tạo ra ba ~K~-mer: {ACG}, {CGT} và {GTA}.

Sau một thí nghiệm giải trình tự, các nhà khoa học thu được ~N~ đoạn DNA ~S_1,S_2,\ldots,S_N~ đôi một phân biệt, mỗi đoạn có độ dài đúng bằng ~K~. Họ muốn tái tạo một chuỗi DNA ngắn nhất từ các đoạn đã thu được.

Một chuỗi DNA ~T~ được gọi là {hợp lệ} nếu thỏa mãn đồng thời:

• Mỗi ~S_i~ ~(1\le i\le N)~ xuất hiện ít nhất một lần dưới dạng một đoạn con liên tiếp của ~T~;
• Mọi đoạn con liên tiếp có độ dài ~K~ của ~T~ đều thuộc tập ~\{S_1,S_2,\ldots,S_N\}~.

Như vậy, một đoạn ~S_i~ có thể xuất hiện nhiều lần trong ~T~, nhưng không được xuất hiện bất kỳ ~K~-mer nào nằm ngoài danh sách đã cho.

Ngoài ra, do giới hạn về khả năng lưu trữ, độ dài của ~T~ không được vượt quá ~ N+K-1+R,~ trong đó ~R~ là một số nguyên không âm cho trước.

Yêu cầu: Hãy tìm độ dài nhỏ nhất của một chuỗi DNA hợp lệ thỏa mãn giới hạn trên. Nếu không tồn tại chuỗi như vậy, hãy in ra ~-1~.

Input

Dòng đầu tiên chứa ba số nguyên ~N,K,R~ ~(1\le N\le 2\cdot 10^5,\; 2\le K\le 12,\; 0\le R\le 15)~.

~N~ dòng tiếp theo, dòng thứ ~i~ chứa xâu ~S_i~ có độ dài đúng bằng ~K~, chỉ gồm các ký tự {A}, {C}, {G}, {T}.

Các xâu ~S_i~ được đảm bảo đôi một phân biệt.

Output

In ra một số nguyên duy nhất --- độ dài nhỏ nhất của một chuỗi DNA hợp lệ thỏa mãn giới hạn đã cho, hoặc ~-1~ nếu không tồn tại.

Sample input 1

5 2 1
AC
AG
AT
CG
GA

Sample output 1

7

Giải thích

Chuỗi {ACGAGAT} có độ dài 7 và chứa đầy đủ năm đoạn đã cho. Đoạn {GA} xuất hiện hai lần. Không tồn tại chuỗi hợp lệ có độ dài 6.

Sample input 2

5 2 0
AC
AG
AT
CG
GA

Sample output 2

-1

Giải thích

Cần ít nhất 7 ký tự để tạo thành một chuỗi hợp lệ, trong khi giới hạn độ dài là 5+2-1=6.

Sample input 3

2 3 9
ACT
GGA

Sample output 3

-1

Giải thích

Không thể tạo một chuỗi chứa đồng thời hai đoạn đã cho mà không xuất hiện thêm một 3-mer nằm ngoài danh sách.

Subtasks

• Có 15\% test ứng với ~N \le 10, K \le 4~.
• Có 20\% test ứng với ~N \le 3000, K \le 7, R=0.~
• Có 25\% test ứng với ~N \le 8000, K \le 9, R \le 5.~
• Có 40\% test không có ràng buộc gì thêm.