F - Best Concatenation Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

1 から 9 の数字および X のみからなる N 個の文字列 S_1, S_2, \ldots, S_N が与えられます。

(1, 2, \ldots, N) を並べ替えた列 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 の長さを表します）。
T のスコアは、スコアが 0 の状態から始め、下記の 9 個の手順を行うことで計算されます。

  • 1 \leq i \lt j \leq |T| および T_i = X かつ T_j = 1 を満たす整数の組 (i, j) の個数だけ、スコアを 1 点加算する 。
  • 1 \leq i \lt j \leq |T| および T_i = X かつ T_j = 2 を満たす整数の組 (i, j) の個数だけ、スコアを 2 点加算する。
  • 1 \leq i \lt j \leq |T| および T_i = X かつ T_j = 3 を満たす整数の組 (i, j) の個数だけ、スコアを 3 点加算する。
  • \cdots
  • 1 \leq i \lt j \leq |T| および T_i = X かつ T_j = 9 を満たす整数の組 (i, j) の個数だけ、スコアを 9 点加算する。

P を任意に選ぶときの、T のスコアとしてあり得る最大値を出力してください。

制約

  • 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 以下

入力

入力は以下の形式で標準入力から与えられる。

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 のスコアは次の通り計算されます。

  • 1 \leq i \lt j \leq |T| および T_i = X かつ T_j = 1 を満たす整数の組 (i, j) が 3 個あり、
  • 1 \leq i \lt j \leq |T| および T_i = X かつ T_j = 3 を満たす整数の組 (i, j) が 4 個あり、
  • 1 \leq i \lt j \leq |T| および T_i = X かつ T_j = 5 を満たす整数の組 (i, j) が 4 個あり、
  • 1 \leq i \lt 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 であり、これが考えられる最大値です。

入力例 2

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

出力例 2

3010

Score : 500 points

Problem Statement

You are given N strings S_1, S_2, \ldots, S_N consisting of digits from 1 through 9 and the character X.

We will choose a permutation P = (P_1, P_2, \ldots, P_N) of (1, 2, \ldots, N) to construct a string T = S_{P_1} + S_{P_2} + \cdots + S_{P_N}, where + denotes a concatenation of strings.

Then, we will calculate the "score" of the string T = T_1T_2\ldots T_{|T|} (where |T| denotes the length of T).
The score is calculated by the following 9 steps, starting from the initial score 0:

  • Add 1 point to the score as many times as the number of integer pairs (i, j) such that 1 \leq i \lt j \leq |T|, T_i = X, and T_j = 1.
  • Add 2 points to the score as many times as the number of integer pairs (i, j) such that 1 \leq i \lt j \leq |T|, T_i = X, and T_j = 2.
  • Add 3 points to the score as many times as the number of integer pairs (i, j) such that 1 \leq i \lt j \leq |T|, T_i = X, and T_j = 3.
  • \cdots
  • Add 9 points to the score as many times as the number of integer pairs (i, j) such that 1 \leq i \lt j \leq |T|, T_i = X, and T_j = 9.

Find the maximum possible score of T when P can be chosen arbitrarily.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • N is an integer.
  • S_i is a string of length at least 1 consisting of digits from 1 through 9 and the character X.
  • The sum of lengths of S_1, S_2, \ldots, S_N is at most 2 \times 10^5.

Input

Input is given from Standard Input in the following format:

N
S_1
S_2
\vdots
S_N

Output

Print the answer.

Sample Input 1

3
1X3
59
XXX

Sample Output 1

71

When P = (3, 1, 2), we have T = S_3 + S_1 + S_2 = XXX1X359. Then, the score of T is calculated as follows:

  • there are 3 integer pairs (i, j) such that 1 \leq i \lt j \leq |T|, T_i = X, and T_j = 1;
  • there are 4 integer pairs (i, j) such that 1 \leq i \lt j \leq |T|, T_i = X, and T_j = 3;
  • there are 4 integer pairs (i, j) such that 1 \leq i \lt j \leq |T|, T_i = X, and T_j = 5;
  • there are 4 integer pairs (i, j) such that 1 \leq i \lt j \leq |T|, T_i = X, and T_j = 9.

Therefore, the score of T is 1 \times 3 + 3 \times 4 + 5 \times 4 + 9 \times 4 = 71, which is the maximum possible value.

Sample Input 2

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

Sample Output 2

3010