Description

Lweb is facing a mountain of English words and falls into deep thought: how can I finish learning quickly and then go play Sanguosha (pinyin)? At this moment, the wise Teacher Feng drifts over from afar. He gives Lweb a planner and a big jar of pickled chili peppers. His planner looks like this:

Then Teacher Feng tells Lweb: I know there are $n$ words you need to learn. We will fill the planner from top to bottom. For the word with index $x$ (the positions $1,\dots ,x-1$ have already been filled):

1. If there exists a word that is its suffix and has not yet been filled into the table, then he needs to eat $n \times n$ chili peppers to learn it.
2. If all of its suffixes have already been filled into the table, and none of the words at positions $1,\dots ,x-1$ is its suffix, then you can remember it by eating $x$ chili peppers.
3. If all of its suffixes have already been filled into the table, and among positions $1,\dots ,x-1$ there exists a word that is its suffix, let the maximum index among its suffixes be $y$. Then you only need to eat $x-y$ chili peppers to remember it.

Lweb is a strange kid who goes berserk when he eats spicy things, so please help Lweb find an optimal way to fill the words so that he learns these $n$ words while eating the fewest chili peppers.

Formal statement:

You need to arrange an order for $n$ strings. Each string incurs a certain cost.

For a string $s$ at position $x$:

1. If there exists at least one other string that is a suffix of $s$, and that string’s position is after $s$, then $s$ incurs a cost of $n \times n$.
2. If no other string is a suffix of $s$, then $s$ incurs a cost of $x$.
3. If all strings that are suffixes of $s$ appear before $s$, and the maximum position among them is $y$, then $s$ incurs a cost of $x-y$.

Arrange an order for the $n$ strings to minimize the total cost.

Input Format

Input an integer $n$, the number of words Lweb needs to learn.

Then follow $n$ lines, each containing one word (lowercase letters only, and all words are pairwise distinct).

Output Format

The minimum number of chili peppers Lweb needs to eat.

2
a
ba

2

Hint

Constraints: $1\le n\le100000$, and the total length of all strings satisfies $1\le \sum|S| \le510000$.

Translated by ChatGPT 5