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 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$.
At 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)$.
For 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.
Before 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.
For example, you can spend $C_{1 , 3}$ to convert string $131233$ into string $313211$.
To help poor girl Setsuna, you are required to find the minimum cost of coins to finish the game.
The 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}$.
Output one integer indicating the minimum cost.
In 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 , 2} = 2$ coins. So the total cost is $4$ coins.
## Input
The 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}$.
## Output
Output one integer indicating the minimum cost.
[samples]
## Note
In 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.
**Definitions**
Let $ M, N \in \mathbb{Z}^+ $ denote the number of guards and couples, respectively.
Let $ G = \{ (L_i, R_i, X_i) \mid i \in \{1, \dots, M\} \} $ be the set of guards, where:
- $ L_i, R_i \in \mathbb{Z} $ are the start and end times of guard $ i $’s duty,
- $ X_i \in \mathbb{Z}^+ $ is the position on the number line where guard $ i $ is stationed.
Let $ 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 $.
Let $ z \in \mathbb{R} $ be a fixed luckiness factor such that $ 0 < z < 0.1 $.
Each guard $ i $ is active during the time interval $ [L_i - z, R_i - z] $.
Each couple $ j $ starts at position $ 0 $ at time $ T_j $ and walks at speed $ 1 $ unit/sec toward $ +\infty $.
**Constraints**
1. $ 1 \leq M, N \leq 2 \cdot 10^5 $
2. $ 0 \leq L_i < R_i \leq 10^9 $
3. $ 1 \leq X_i \leq 10^9 $
4. $ 0 \leq T_1 < T_2 < \dots < T_N \leq 10^9 $
5. 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 $
**Objective**
For each couple $ j \in \{1, \dots, N\} $:
- Let $ t_{\text{arrive}} = T_j + x $ be the time at which couple $ j $ reaches position $ x $.
- Couple $ j $ is caught if there exists a guard $ i $ such that:
$$
T_j + X_i \in [L_i - z, R_i - z]
$$
i.e.,
$$
L_i - z \leq T_j + X_i \leq R_i - z
$$
- If such a guard $ i $ exists, output $ X_i $ (the distance covered).
- Otherwise, output $ -1 $.
**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:
$$
L_i \leq T_j + X_i < R_i
$$
(because $ T_j + X_i $ is integer, and $ z < 0.1 $ ensures no integer lies strictly between $ R_i - z $ and $ R_i $).
Thus, for each couple $ j $, find the minimal $ X_i $ such that:
$$
L_i \leq T_j + X_i < R_i
$$
If 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.
**Output**
For each couple $ j $, output:
$$
\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
$$