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

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.