{"problem":{"name":"Best Concatenation","description":{"content":"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 ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc268_f"},"statements":[{"statement_type":"Markdown","content":"You are given $N$ strings $S_1, S_2, \\ldots, S_N$ consisting of digits from `1` through `9` and the character `X`.\nWe 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.\nThen, we will calculate the \"score\" of the string $T = T_1T_2\\ldots T_{|T|}$ (where $|T|$ denotes the length of $T$).  \nThe score is calculated by the following $9$ steps, starting from the initial score $0$:\n\n*   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`.\n*   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`.\n*   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`.\n*   $\\cdots$\n*   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`.\n\nFind the maximum possible score of $T$ when $P$ can be chosen arbitrarily.\n\n## Constraints\n\n*   $2 \\leq N \\leq 2 \\times 10^5$\n*   $N$ is an integer.\n*   $S_i$ is a string of length at least $1$ consisting of digits from `1` through `9` and the character `X`.\n*   The sum of lengths of $S_1, S_2, \\ldots, S_N$ is at most $2 \\times 10^5$.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$S_1$\n$S_2$\n$\\vdots$\n$S_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc268_f","tags":[],"sample_group":[["3\n1X3\n59\nXXX","71\n\nWhen $P = (3, 1, 2)$, we have $T = S_3 + S_1 + S_2 = $ `XXX1X359`. Then, the score of $T$ is calculated as follows:\n\n*   there are $3$ integer pairs $(i, j)$ such that $1 \\leq i \\lt j \\leq |T|$, $T_i = $ `X`, and $T_j = $ `1`;\n*   there are $4$ integer pairs $(i, j)$ such that $1 \\leq i \\lt j \\leq |T|$, $T_i = $ `X`, and $T_j = $ `3`;\n*   there are $4$ integer pairs $(i, j)$ such that $1 \\leq i \\lt j \\leq |T|$, $T_i = $ `X`, and $T_j = $ `5`;\n*   there are $4$ integer pairs $(i, j)$ such that $1 \\leq i \\lt j \\leq |T|$, $T_i = $ `X`, and $T_j = $ `9`.\n\nTherefore, the score of $T$ is $1 \\times 3 + 3 \\times 4 + 5 \\times 4 + 9 \\times 4 = 71$, which is the maximum possible value."],["10\nX63X395XX\nX2XX3X22X\n13\n3716XXX6\n45X\nX6XX\n9238\n281X92\n1XX4X4XX6\n54X9X711X1","3010"]],"created_at":"2026-03-03 11:01:14"}}