该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

附加文件

题目描述

有 $N$ 个字符串，全部由小写字母组成。字符串两两不同。

现在要对它们进行排序。

排序后，每个字符串有一个代价。

对于排在第 $i$ 个位置的字符串 $S$，它的代价计算方法是：

• 如果在 $S$ 的前后均不存在字符串是 $S$ 的后缀，那么 $S$ 的代价为 $i$ ；
• 如果在 $S$ 的后面存在字符串是 $S$ 的后缀，那么不论 $S$ 的前面是否存在字符串是 $S$ 的后缀， $S$ 的代价均为 $N^2$ ；
• 如果在 $S$ 的后面不存在字符串是 $S$ 的后缀，但在 $S$ 的前面存在字符串是 $S$ 的后缀，则找到离 $S$ 最近的那个后缀，记其位置为 $j$，那么 $S$ 的代价为 $i-j$ 。

排序总代价为排序后每个字符串的代价之和。

请你找到一种排序方式，使得排序总代价最小。

你只需要输出最小的排序总代价。

输入

第一行：一个整数 $N$

接下来 $N$ 行，每行一个字符串。

输出

一个整数，表示最小的排序总代价。

样例输入

2
a
ba

样例输出

2

样例解释

对于样例中的两个字符串 a , ba，有以下两种排序方式：

1、a , ba

• a 排在第 1 个位置，前后均不存在它的后缀，所以 a 的代价为 1
• ba 排在第 2 个位置，前面存在它的后缀 a，离它最近，位置为 1，所以 ba 的代价为 2-1=1

总代价为 1 + 1 = 2；

2、ba , a

• ba 排在第 1 个位置，后面存在它的后缀 a，所以 ba 的代价为 $2^2$ =4；
• a 排在第 2 个位置，前后均不存在它的后缀，所以 a 的代价为 2

总代价为 4 + 2 = 6。

综上，最小的排序总代价为 2。

数据范围

$1 ≤ N ≤ 100,000$，所有字符串的长度之和不超过 $600,000$。