题目背景

一座城市中有若干地点，每个地点都用一个小写字符串作为名称。

任意两个地点之间都有一条道路。两个地点的名称越相似，它们之间道路的费用就可能越低。现在需要规划一条路线，从指定的起点出发，恰好访问每个地点一次，并最终到达指定终点。

请计算这条路线的最小总费用。

题目描述

给定一个包含 $N$ 个顶点的无向完全图，顶点编号为：

$$0,1,\ldots,N-1.$$

顶点 $i$ 的标签为字符串 $s_i$。

对于两个字符串 $A$ 和 $B$，定义：

• $|A|$ 表示字符串 $A$ 的长度；
• $\operatorname{LCP}(A,B)$ 表示 $A$ 和 $B$ 的最长公共前缀；
• $|\operatorname{LCP}(A,B)|$ 表示最长公共前缀的长度。

顶点 $i$ 与顶点 $j$ 之间的边权为：

$$w(i,j) = |s_i|^2 + |s_j|^2 - |\operatorname{LCP}(s_i,s_j)|^2.$$

由于该公式关于 $i,j$ 对称，因此图是无向图。

一条哈密顿路径是一个顶点序列：

$$a_1,a_2,\ldots,a_N,$$

满足：

• 所有 $a_i$ 两两不同；
• 对于每个 $2\le i\le N$，顶点 $a_{i-1}$ 与 $a_i$ 之间有边。

由于本题给出的图是完全图，因此任意顶点排列都是一条哈密顿路径。

路径的费用等于相邻顶点之间边权之和：

$$\sum_{i=2}^{N}w(a_{i-1},a_i).$$

请在所有满足以下条件的哈密顿路径中，求最小费用：

• 路径从顶点 $0$ 开始，即 $a_1=0$；
• 路径在顶点 $1$ 结束，即 $a_N=1$。

最长公共前缀

一个字符串的前缀可以通过删除其末尾的若干个连续字符得到，也可以不删除任何字符。

两个字符串的最长公共前缀，是同时作为这两个字符串前缀的最长字符串。

例如：

• abcd 与 abef 的最长公共前缀为 ab，长度为 $2$；
• home 与 pub 的最长公共前缀为空串，长度为 $0$；
• abc 与 abc 的最长公共前缀为 abc，长度为 $3$。

输入格式

第一行包含一个整数 $N$，表示顶点数量。

接下来 $N$ 行，第 $i+1$ 行包含字符串 $s_i$，表示顶点 $i$ 的标签。

特别地：

• 输入的第一个字符串是起点顶点 $0$ 的标签；
• 输入的第二个字符串是终点顶点 $1$ 的标签。

输出格式

输出一个整数，表示从顶点 $0$ 出发、访问每个顶点恰好一次并最终到达顶点 $1$ 的哈密顿路径的最小费用。

数据范围

对于所有测试数据：

• $2\le N\le 50$；
• $1\le |s_i|\le 50$；
• 每个字符串只包含小写英文字母；
• 不同顶点的标签可以相同；
• 答案可以使用 $32$ 位有符号整数表示。

样例 1

输入

3
home
school
pub

输出

70

解释

从顶点 $0$ 开始并在顶点 $1$ 结束的哈密顿路径只有：

0 -> 2 -> 1

三个顶点的标签依次为：

home, school, pub

home 与 pub 没有公共前缀，因此：

$$w(0,2)=4^2+3^2=25.$$

pub 与 school 也没有公共前缀，因此：

$$w(2,1)=3^2+6^2=45.$$

总费用为：

$$25+45=70.$$

样例 2

输入

4
school
home
pub
stadium

输出

167

解释

除去固定的起点 $0$ 和终点 $1$，顶点 $2$、$3$ 有两种访问顺序。

先访问标签为 stadium 的顶点，再访问标签为 pub 的顶点，所得路径比另一种顺序少 $1$ 的费用。

样例 3

输入

4
abcd
aecgh
abef
aecd

输出

91

解释

边权矩阵如下，其中 - 表示顶点自身：

-  40 28 31
40 -  40 32
28 40 -  31
31 32 31 -

最优路径为：

abcd -> abef -> aecd -> aecgh

也就是：

0 -> 2 -> 3 -> 1

总费用为：

$$28+31+32=91.$$

样例 4

输入

2
manglisi
tbilisi

输出

113

样例 5

输入

2
a
a

输出

1

解释

两个字符串完全相同，最长公共前缀长度为 $1$，因此：

$$1^2+1^2-1^2=1.$$