# 2020 年 “联想杯”全国高校程序设计在线邀请赛暨第三届上海理工大学程序设计竞赛

E. Eight Digital Games
PDF 题面可用

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.

### 样例

Input
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

Output
2

Input
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

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

NaN