AT_abc268_f [ABC268F] Best Concatenation

[problemUrl]: https://atcoder.jp/contests/abc268/tasks/abc268_f `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 $ のスコアとしてあり得る最大値を出力してください。

入力は以下の形式で標準入力から与えられる。 > $ 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 $ 以下 ### Sample Explanation 1 $ 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 $ であり、これが考えられる最大値です。