AT_abc268_f.[ABC268F] Best Concatenation

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

你可以任选一个 $1$ 到 $N$ 的排列 $P = (P_1, P_2, \ldots, P_N)$，并将字符串 $S_{P_1}, S_{P_2}, \ldots, S_{P_N}$ 按顺序连接，得到字符串 $T = S_{P_1} + S_{P_2} + \cdots + S_{P_N}$。这里的 $+$ 表示字符串的连接操作。

然后，对字符串 $T = T_1T_2\ldots T_{|T|}$ 计算其“得分”（$|T|$ 表示 $T$ 的长度）。
$T$ 的得分从 $0$ 开始，按照以下 $9$ 个步骤计算：

• 对于所有满足 $1 \leq i < j \leq |T|$ 且 $T_i = $ X 且 $T_j = $ 1 的整数对 $(i, j)$，每对使得得分加 $1$。
• 对于所有满足 $1 \leq i < j \leq |T|$ 且 $T_i = $ X 且 $T_j = $ 2 的整数对 $(i, j)$，每对使得得分加 $2$。
• 对于所有满足 $1 \leq i < j \leq |T|$ 且 $T_i = $ X 且 $T_j = $ 3 的整数对 $(i, j)$，每对使得得分加 $3$。
• $\cdots$
• 对于所有满足 $1 \leq i < j \leq |T|$ 且 $T_i = $ X 且 $T_j = $ 9 的整数对 $(i, j)$，每对使得得分加 $9$。

请输出在任意选择排列 $P$ 时，$T$ 的得分可能取得的最大值。

输入按以下格式从标准输入读入。

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

输出答案。

数据范围

• $2 \leq N \leq 2 \times 10^5$
• $N$ 为整数
• $S_i$ 是仅由数字 $1$ 到 $9$ 以及 X 组成的字符串，长度至少为 $1$
• $S_1, S_2, \ldots, S_N$ 的总长度不超过 $2 \times 10^5$

样例解释 1

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

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

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

由 ChatGPT 4.1 翻译