最佳拼接

题目描述

给定 $N$ 个由数字 $1$ 到 $9$ 和字符 X 组成的字符串 $S_1, S_2, \ldots, S_N$。

我们选择 $(1, 2, \ldots, N)$ 的一个排列 $P = (P_1, P_2, \ldots, P_N)$ 来构造字符串 $T = S_{P_1} + S_{P_2} + \cdots + S_{P_N}$，其中 $+$ 表示字符串的连接。

然后计算字符串 $T = T_1T_2\ldots T_{|T|}$ 的「得分」（其中 $|T|$ 表示 $T$ 的长度）。

得分从初始值 $0$ 开始，通过以下 $9$ 个步骤计算：

• 满足 $1 \le i \lt j \le |T|$、$T_i =$ X 且 $T_j =$ 1 的整数对 $(i, j)$ 每有一对，得分加 $1$ 分。
• 满足 $1 \le i \lt j \le |T|$、$T_i =$ X 且 $T_j =$ 2 的整数对 $(i, j)$ 每有一对，得分加 $2$ 分。
• 满足 $1 \le i \lt j \le |T|$、$T_i =$ X 且 $T_j =$ 3 的整数对 $(i, j)$ 每有一对，得分加 $3$ 分。
• $\cdots$
• 满足 $1 \le i \lt j \le |T|$、$T_i =$ X 且 $T_j =$ 9 的整数对 $(i, j)$ 每有一对，得分加 $9$ 分。

当 $P$ 可以任意选择时，求 $T$ 的得分的最大值。

输入格式

输入按以下格式从标准输入给出：

$N$
$S_1$
$S_2$
$\vdots$
$S_N$

输出格式

输出答案。

样例

3
1X3
59
XXX

71

当 $P = (3, 1, 2)$ 时，$T = S_3 + S_1 + S_2 =$ XXX1X359。 此时 $T$ 的得分计算如下：

• 满足 $1 \le i \lt j \le |T|$、$T_i =$ X 且 $T_j =$ 1 的整数对有 $3$ 个；
• 满足 $1 \le i \lt j \le |T|$、$T_i =$ X 且 $T_j =$ 3 的整数对有 $4$ 个；
• 满足 $1 \le i \lt j \le |T|$、$T_i =$ X 且 $T_j =$ 5 的整数对有 $4$ 个；
• 满足 $1 \le i \lt j \le |T|$、$T_i =$ X 且 $T_j =$ 9 的整数对有 $4$ 个。

因此 $T$ 的得分为 $1 \times 3 + 3 \times 4 + 5 \times 4 + 9 \times 4 = 71$，这是能达到的最大值。

10
X63X395XX
X2XX3X22X
13
3716XXX6
45X
X6XX
9238
281X92
1XX4X4XX6
54X9X711X1

3010

数据范围

• $2 \le N \le 2 \times 10^5$
• $N$ 是整数。
• $S_i$ 是由数字 $1$ 到 $9$ 和字符 X 组成的长度至少为 $1$ 的字符串。
• $S_1, S_2, \ldots, S_N$ 的长度之和至多为 $2 \times 10^5$。