单点时限: 1.0 sec
内存限制: 256 MB
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 \lt j$ and $S_{i} \gt 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\le x,y\le 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 \leq n \leq 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 \leq P_{i,j} \leq 10^7)$. It is guaranteed that $P_{i,j}=0$ holds for $i \leq j$.
The next $8$ lines contains $8$ integers each, where the $j$-th integer of the $i$-th line is $C_{i,j}(0 \leq C_{i,j} \leq 10^{12})$. It is guaranteed that $C_{i,i}=0$ and $C_{i,j}=C_{j,i}$.
Output one integer indicating the minimum cost.
5 54321 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0
2
6 222112 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 0 0 1 2 2 2 2 2 2 1 0 2 2 2 2 2 2 2 2 0 2 2 2 2 2 2 2 2 0 2 2 2 2 2 2 2 2 0 2 2 2 2 2 2 2 2 0 2 2 2 2 2 2 2 2 0 2 2 2 2 2 2 2 2 0
4
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.