Bạn có một máy in và cần in \(n\) từ để ghép thành một khẩu hiệu. Máy in có một khay để xếp các miếng kim loại (mỗi miếng chứa một kí tự) để tạo thành từ. Ban đầu khay rỗng, mỗi lượt bạn được thao tác một trong ba loại sau:

• Xếp thêm một miếng kim loại chứa một kí tự vào cuối khay;
• Loại bỏ một miếng kim loại chứa một kí tự ở cuối khay;
• In ra từ được tạo bởi các kí tự trên khay.

Vào cuối quá trình in, bạn được phép để lại các miếng kim loại trên khay, ngoài ra bạn được phép in các từ theo bất kì thứ tự nào.

Yêu cầu: Cho \(n\) từ, hãy tính số thao tác ít nhất để in được \(n\) từ đó.

Input

• Dòng đầu chứa số nguyên dương \(n\).
• Tiếp theo là \(n\) dòng, mỗi dòng chứa một từ cần in, các từ chỉ gồm các kí tự a đến z và tổng số các kí tự không vượt quá \(10^6\).

Output

• Gồm một dòng duy nhất chứa số thao tác ít nhất cần thực hiện để in \(n\) từ trên.

Constraints

• Subtask \(1\) (\(20\%\) số điểm): \(n \le 20\).
• Subtask \(2\) (\(80\%\) số điểm): Không có ràng buộc gì thêm.

Example

3
print
the
poem

20

Nguồn: Thầy Đông '21