408285: GYM103076 H 8 Game

H. 8 Gametime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

The 8 game consists of a 3x3 matrix. Each cell has a distinct number between 1 and 8 or a white space.

Let $$$0$$$ be a representation for a cell that contains a white space, we want to do a sequence of operations, possibly zero, such that the matrix becomes $$$$$$\begin{pmatrix}1 & 2 & 3\\\ 4 & 5 & 6\\\ 7 & 8 & 0\end{pmatrix}$$$$$$

Let $$$M$$$ be the given matrix, if $$$M_{i,j} == 0$$$, then you can do four operations:

• Swap $$$M_{i,j}$$$ with $$$M_{i,j+1}$$$, if $$$j < 3$$$
• Swap $$$M_{i,j}$$$ with $$$M_{i,j-1}$$$, if $$$j > 1$$$
• Swap $$$M_{i,j}$$$ with $$$M_{i+1,j}$$$, if $$$i < 3$$$
• Swap $$$M_{i,j}$$$ with $$$M_{i-1,j}$$$, if $$$i > 1$$$

Let's assume you swapped $$$M_{i,j}$$$ with $$$M_{i',j'}$$$, and let $$$x == M_{i',j'}$$$, then this operation has $$$Cost_x$$$ of cost.

$$$Cost_x$$$ is the swap cost for each number $$$x$$$, $$$1 <= x <= 8$$$.

Kinho loves the 8 game, but now he is very busy developing his 3D game library, so he asks you to solve this problem.

Given the initial matrix and the cost to move each number, say what is the minimum cost necessary to order the matrix in the requested way.

Input

The input consists of four lines. The three initial lines contains three distincts integers each. $$$0 <= M_{i,j} <= 8$$$, where $$$0$$$ represents a white space cell. The fourth line contains eight integers, where the $$$i$$$-th integer represents the cost $$$Cost_i$$$ to swap the cell with the number $$$i$$$. $$$1 <= Cost_i <= 10^9, 1 <= i <= 8$$$

Output

Print a single integer, the minimum cost to reorganize the matrix. In the given input, there is always a valid answer.

ExamplesInput

5 4 0
6 1 8
7 3 2
1 1 1 1 1 1 1 1

Output

22

Input

1 2 3
4 5 6
7 8 0
1 1 1 1 1 1 1 1

Output

0