{"problem":{"name":"E. Eight Digital Games","description":{"content":"Setsuna has been obsessed with an electronic video game called \"Eight Digital\". It is a puzzle game which is too difficult for Setsuna, so she has been stuck in the first level for a long time. In th","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10262E"},"statements":[{"statement_type":"Markdown","content":"Setsuna has been obsessed with an electronic video game called \"Eight Digital\". It is a puzzle game which is too difficult for Setsuna, so she has been stuck in the first level for a long time.\n\nIn the game, you have a string of length $n$ containing only digits from $1$ to $8$. Let's call this string $S$, $S_i$ denotes the $i$-th character of $S$. \n\nAt the end of the game, the game system will calculate the penalties of inversions, and will deduct your coins. Inversion is a pair $(i, j)$ which satisfies both $i < j$ and $S_i > S_j$. The game system will deduct you $P_{S_i , S_j}$ coins for each inversion $(i, j)$.\n\nFor example, string $85511$ will cost you $2 times P_{8 , 5} + 2 times P_{8 , 1} + 4 times P_{5 , 1}$ coins, and string $1234$ will cost you $0$ coins.\n\nBefore the end of the game, you can do *arbitrary* times of the operation. Each operation is to select two different numbers $x$ and $y (1 <= x, y <= 8)$, then all $x$ in the string will become $y$, and all $y$ will become $x$ and the game system will deduct you $C_{x , y}$ coins.\n\nFor example, you can spend $C_{1 , 3}$ to convert string $131233$ into string $313211$.\n\nTo help poor girl Setsuna, you are required to find the minimum cost of coins to finish the game.\n\nThe first line contains one integer $n (1 <= n <= 3 * 10^5)$.\n\nThe second line contains a string $S$. It is guaranteed that the length of $S$ is $n$ and $S$ only contains digits from $1$ to $8$.\n\nThe next $8$ lines contains $8$ integers each, where the $j$-th integer of the $i$-th line is $P_{i , j} (0 <= P_{i , j} <= 10^7)$. It is guaranteed that $P_{i , j} = 0$ holds for $i <= j$.\n\nThe next $8$ lines contains $8$ integers each, where the $j$-th integer of the $i$-th line is $C_{i , j} (0 <= C_{i , j} <= 10^(12))$. It is guaranteed that $C_{i , i} = 0$ and $C_{i , j} = C_{j , i}$.\n\nOutput one integer indicating the minimum cost.\n\nIn sample $1$, you can spend $1$ coin to convert $54321$ into $14325$. Then, spend another $1$ coin to convert it into $12345$. \n\nIn sample $2$, you can spend $2$ coins to convert $222112$ into $222882$, then end the game. The inversions $(4, 6)$ and $(5, 6)$ will cost you $2 times P_{8 , 2} = 2$ coins. So the total cost is $4$ coins.\n\n## Input\n\nThe first line contains one integer $n (1 <= n <= 3 * 10^5)$.The second line contains a string $S$. It is guaranteed that the length of $S$ is $n$ and $S$ only contains digits from $1$ to $8$.The next $8$ lines contains $8$ integers each, where the $j$-th integer of the $i$-th line is $P_{i , j} (0 <= P_{i , j} <= 10^7)$. It is guaranteed that $P_{i , j} = 0$ holds for $i <= j$.The next $8$ lines contains $8$ integers each, where the $j$-th integer of the $i$-th line is $C_{i , j} (0 <= C_{i , j} <= 10^(12))$. It is guaranteed that $C_{i , i} = 0$ and $C_{i , j} = C_{j , i}$.\n\n## Output\n\nOutput one integer indicating the minimum cost.\n\n[samples]\n\n## Note\n\nIn sample $1$, you can spend $1$ coin to convert $54321$ into $14325$. Then, spend another $1$ coin to convert it into $12345$. In sample $2$, you can spend $2$ coins to convert $222112$ into $222882$, then end the game. The inversions $(4, 6)$ and $(5, 6)$ will cost you $2 times P_(8 comma 2) = 2$ coins. So the total cost is $4$ coins.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ M, N \\in \\mathbb{Z}^+ $ denote the number of guards and couples, respectively.  \nLet $ G = \\{ (L_i, R_i, X_i) \\mid i \\in \\{1, \\dots, M\\} \\} $ be the set of guards, where:  \n- $ L_i, R_i \\in \\mathbb{Z} $ are the start and end times of guard $ i $’s duty,  \n- $ X_i \\in \\mathbb{Z}^+ $ is the position on the number line where guard $ i $ is stationed.  \n\nLet $ C = \\{ T_j \\mid j \\in \\{1, \\dots, N\\} \\} $ be the set of start times for couples, with $ T_1 < T_2 < \\dots < T_N $.  \n\nLet $ z \\in \\mathbb{R} $ be a fixed luckiness factor such that $ 0 < z < 0.1 $.  \nEach guard $ i $ is active during the time interval $ [L_i - z, R_i - z] $.  \n\nEach couple $ j $ starts at position $ 0 $ at time $ T_j $ and walks at speed $ 1 $ unit/sec toward $ +\\infty $.  \n\n**Constraints**  \n1. $ 1 \\leq M, N \\leq 2 \\cdot 10^5 $  \n2. $ 0 \\leq L_i < R_i \\leq 10^9 $  \n3. $ 1 \\leq X_i \\leq 10^9 $  \n4. $ 0 \\leq T_1 < T_2 < \\dots < T_N \\leq 10^9 $  \n5. For any $ i \\neq j $, if $ X_i = X_j $, then $ [L_i - z, R_i - z] \\cap [L_j - z, R_j - z] = \\emptyset $  \n\n**Objective**  \nFor each couple $ j \\in \\{1, \\dots, N\\} $:  \n- Let $ t_{\\text{arrive}} = T_j + x $ be the time at which couple $ j $ reaches position $ x $.  \n- Couple $ j $ is caught if there exists a guard $ i $ such that:  \n  $$\n  T_j + X_i \\in [L_i - z, R_i - z]\n  $$\n  i.e.,  \n  $$\n  L_i - z \\leq T_j + X_i \\leq R_i - z\n  $$\n- If such a guard $ i $ exists, output $ X_i $ (the distance covered).  \n- Otherwise, output $ -1 $.  \n\n**Note**: Since $ z \\in (0, 0.1) $, and all inputs are integers, the condition $ T_j + X_i \\in [L_i - z, R_i - z] $ is equivalent to:  \n$$\nL_i \\leq T_j + X_i < R_i\n$$  \n(because $ T_j + X_i $ is integer, and $ z < 0.1 $ ensures no integer lies strictly between $ R_i - z $ and $ R_i $).  \n\nThus, for each couple $ j $, find the minimal $ X_i $ such that:  \n$$\nL_i \\leq T_j + X_i < R_i\n$$  \nIf multiple such $ X_i $ exist (at different positions), the couple is caught at the **first** such position they reach — i.e., the **smallest** $ X_i $ satisfying the condition.  \n\n**Output**  \nFor each couple $ j $, output:  \n$$\n\\min \\left\\{ X_i \\,\\middle|\\, L_i \\leq T_j + X_i < R_i \\right\\} \\quad \\text{if such } X_i \\text{ exists}, \\quad \\text{else } -1\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10262E","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}