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 翻译