题目内容

小 L 有一个长度为 $n$ 的正整数序列 $A = [a_1, a_2, \dots, a_n]$，每个数在十进制下均不包含数字 $0$。

现在小 L 想要进行一个特殊的操作：将所有数字的每一个十进制数位拆出，得到一个数位池；然后将池中的数位重新分配，构造出 $n$ 个新的正整数。要求第 $i$ 个新数的位数必须与原始的 $a_i$ 的位数相同。

问通过最优的分配方案，所能得到的所有新数的总和最大是多少。

约束：

• 数组长度 $n$ 满足 $1 \le n \le 2 \times 10^5$。
• 每个 $a_i$ 满足 $1 \le a_i \le 10^9$，且十进制各数位中不包含数字 $0$。

输入描述

第一行包含一个整数 $n$，表示数组长度。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，相邻整数之间用空格分隔。

输出描述

输出一个整数，表示所能获得的最大总和。

样例1

输入

1
123

输出

321

说明

只有 $n=1$ 个数 123，它包含 3 个十进制数位。将所有数位拆开得到数字池 $\{1,2,3\}$。新数的位数固定为 3。为了最大化该数，应将最大的数字 3 放在权重最高的百位（$10^2$），2 放在十位（$10^1$），1 放在个位（$10^0$），得到最大值为 $3 \times 100 + 2 \times 10 + 1 = 321$。因此最大总和为 321。

样例2

输入

2
9 12

输出

93

说明

两个数 9 和 12，长度分别为 1 和 2。数字池包含数字 9, 1, 2；权重池包含一个 $10^0$（来自 9 的个位）以及一个 $10^0$ 和一个 $10^1$（来自 12 的个位和十位）。分配时优先满足高权重：唯一的 $10^1$ 分配最大的数字 9，贡献 $9 \times 10 = 90$；剩余两个 $10^0$ 分配数字 2 和 1，贡献 $2 + 1 = 3$。总和为 $90 + 3 = 93$。对应构造的新数可以是 92 和 1，或 91 和 2，总和均为 93。

样例3

输入

3
7 8 9

输出

24

说明

三个数 7, 8, 9 均为 1 位数。数字池为 $\{7,8,9\}$，三个权重都是 $10^0$。所有位置等价，任意分配得到的总和均为 $7+8+9=24$。这是唯一可能的总和，也是最大值 24。

样例4

输入

1
1

输出

1

说明

仅一个数字 1，且长度固定为 1。构造的新数只能是 1，总和为 1。