分数: 500 点
问题陈述
你被给予 N 字符串 S_1, S_2, \ldots, S_N 由以下数字组成 1 通过 9 和角色 X.
我们将选择一个排列 P = (P_1, P_2, \ldots, P_N) of (1, 2, \ldots, N) 构造一个字符串 T = S_{P_1} + S_{P_2} + \cdots + S_{P_N},其中 + 表示字符串的串联。
然后,我们将计算字符串的“分数” T = T_1T_2\ldots T_{|T|} (其中 |T| 表示长度 T).
分数的计算方式如下 9 步数,从初始分数开始 0:
- 添加 1 指向分数的次数与整数对的数量相同 (i, j) 这样 1 \leq i \lt j \leq |T|, T_i =
X,和 T_j =1. - 添加 2 指向分数的次数与整数对的数量相同 (i, j) 这样 1 \leq i \lt j \leq |T|, T_i =
X,和 T_j =2. - 添加 3 指向分数的次数与整数对的数量相同 (i, j) 这样 1 \leq i \lt j \leq |T|, T_i =
X,和 T_j =3. - \cdots
- 添加 9 指向分数的次数与整数对的数量相同 (i, j) 这样 1 \leq i \lt j \leq |T|, T_i =
X,和 T_j =9.
找出以下的最大可能分数 T 当 P 可以任意选择。
约束
- 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 \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 is 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