Mảnh Ghép Lời Tiên Tri

Giáo sư Sybill Trelawney vừa phát hiện $N$ mảnh giấy cổ trong Phòng Tiên Tri tại Bộ Phép Thuật. Mỗi mảnh giấy chứa một đoạn ký tự - là một phần của lời tiên tri vĩ đại. Bà tin rằng lời tiên tri hoàn chỉnh là một xâu ký tự ngắn nhất có thể sao cho mỗi mảnh giấy đều xuất hiện như một xâu con liên tiếp (substring) trong xâu đó.

Hãy giúp Giáo sư Trelawney tìm độ dài của lời tiên tri ngắn nhất chứa tất cả các mảnh giấy.

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên $N$ - số mảnh giấy.
• $N$ dòng tiếp theo, mỗi dòng chứa một xâu ký tự gồm các chữ cái Latin thường - nội dung mảnh giấy thứ $i$.

Dữ liệu ra

In ra một số nguyên duy nhất - độ dài ngắn nhất của lời tiên tri chứa tất cả các mảnh giấy.

Ràng buộc

• $1\le N\le 18$
• Mỗi xâu có độ dài từ $1$ đến $1000$
• Tổng độ dài tất cả các xâu không quá $10000$
• Các xâu chỉ chứa chữ cái Latin thường

Ví dụ