406946: GYM102623 E Eight Digital Games

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\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 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 \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.