问题描述

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

我们将选择一个排列 $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$ 开始：

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

找到当 $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$

输出

打印答案。

示例输入 1

3
1X3
59
XXX

示例输出 1

71

当 $P = (3, 1, 2)$ 时，我们有 $T = S_3 + S_1 + S_2 =$ XXX1X359。然后，计算 $T$ 的分数如下：

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

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

示例输入 2

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

示例输出 2

3010