F - 最佳串联

得分：$500$ 分

题目描述

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

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

然后，我们将根据以下 $9$ 个步骤来计算字符串 $T = T_1T_2\ldots T_{|T|}$（其中 $|T|$ 表示 $T$ 的长度）的"得分"，以初始得分 $0$ 为起点：

• 将得分加 $1$ 分，数量为满足 $1 \leq i \lt j \leq |T|$，$T_i = $ X，$T_j = $ 1 的整数对 $(i, j)$ 的个数。
• 将得分加 $2$ 分，数量为满足 $1 \leq i \lt j \leq |T|$，$T_i = $ X，$T_j = $ 2 的整数对 $(i, j)$ 的个数。
• 将得分加 $3$ 分，数量为满足 $1 \leq i \lt j \leq |T|$，$T_i = $ X，$T_j = $ 3 的整数对 $(i, j)$ 的个数。
• $\cdots$
• 将得分加 $9$ 分，数量为满足 $1 \leq i \lt j \leq |T|$，$T_i = $ X，$T_j = $ 9 的整数对 $(i, j)$ 的个数。

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

约束

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

输入

输入在形如下面的标准输入中给出：

$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$ 的得分如下计算：

• 有 $3$ 个整数对 $(i, j)$ 满足 $1 \leq i \lt j \leq |T|$，$T_i = $ X，$T_j = $ 1；
• 有 $4$ 个整数对 $(i, j)$ 满足 $1 \leq i \lt j \leq |T|$，$T_i = $ X，$T_j = $ 3；
• 有 $4$ 个整数对 $(i, j)$ 满足 $1 \leq i \lt j \leq |T|$，$T_i = $ X，$T_j = $ 5；
• 有 $4$ 个整数对 $(i, j)$ 满足 $1 \leq i \lt j \leq |T|$，$T_i = $ X，$T_j = $ 9。

因此，$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