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

Chuỗi từ có độ dài n là một dãy các từ w₁, w₂, ..., w_n sao cho với mọi 1 ≤ i < n, từ w_i là tiền tố của từ w_i+1.

Nhắc lại từ u có độ dài k là tiền tố của từ v có độ dài l nếu l > k và các ký tự đầu tiên của v trùng với từ u.

Cho tập hợp các từ S={s₁, s₂, ..., s_m}. Tìm chuỗi từ dài nhất có thể xây dựng được bằng cách dùng các từ trong tập hợp S (có thể không sử dụng hết các từ).

Dữ liệu

Dòng đầu tiên chứa số nguyên m (1 ≤ m ≤ 250000). Mỗi dòng trong số m dòng sau chứa một từ trong tập S.

Biết rằng mỗi từ có độ dài không quá 250000 ký tự và tổng độ dài của các từ không vượt quá 250000 ký tự.

Kết quả

In ra một số duy nhất là độ dài của chuỗi từ dài nhất xây dựng được từ các từ trong tập đã cho.

Ví dụ

Dữ liệu
3
a
ab
abc

Kết quả
3

Dữ liệu
5
a
ab
bc
bcd
add

Kết quả
2

Nguồn: Цикл Интернет-олимпиад для школьников, сезон 2007-2008