Problem Description

The Antarctic Sea is represented by a grid of size $H \times W$. The part of the sea from the top $ i $-th row and from the left $ j $-th column is denoted as $ (i, j) $.

There are many icebergs in the Antarctic Sea. Iroha, the explorer, wants to move from $ (s_x, s_y) $ to $ (g_x, g_y) $ by repeatedly moving to adjacent cells up, down, left, or right. She cannot move to a cell with an iceberg, so she may need to melt some icebergs.

Each iceberg has a fixed cost to melt. The cost to melt all the icebergs of the $ k $-th type is $ C_k $ yen. What is the minimum cost for Iroha to reach from $ (s_x, s_y) $ to $ (g_x, g_y) $?

There are $ X $ types of icebergs. The state of the cell $ (i, j) $ is represented by $ A_{i,j} $. When $ A_{i,j} = 0 $, this cell has no iceberg. When $1 \leq A_{i,j} \leq X$, this cell has an iceberg of type $ A_{i,j} $. Icebergs with the same number are connected vertically and horizontally.

Input Format

The input is given from the standard input in the following format:

$ H $ $ W $ $ X $ $ s_x $ $ s_y $ $ g_x $ $ g_y $ $ A_{1, 1} $ $A_{1, 2} \cdots A_{1, W}$ $ A_{2, 1} $ $A_{2, 2} \cdots A_{2, W}$ $\vdots$ $ A_{H, 1} $ $A_{H, 2} \cdots A_{H, W}$ $ C_1 $ $C_2 \cdots C_X$

Output Format

Output the minimum cost for Iroha to reach from the start to the goal.

Sample Input and Output

Sample Input #1

4 5 4
2 1
3 5
1 1 1 2 2
0 1 0 2 0
0 3 0 4 0
3 3 4 4 4
10 5 8 12

Sample Output #1

13

Sample Input #2

5 7 6
5 3
2 7
2 2 2 1 1 3 3
2 2 2 1 1 3 0
2 6 6 6 1 3 5
2 6 6 6 1 4 4
2 2 0 1 1 4 4
927 138 284 714 456 798

Sample Output #2

1211

Notes/Hints

Constraints

• All inputs are integers.
• $1 \leq H, W \leq 500$
• $1 \leq s_x, g_x \leq H$ (added on 2019/05/01 13:45)
• $1 \leq s_y, g_y \leq W$ (added on 2019/05/01 13:45)
• Both $ (s_x, s_y) $ and $ (g_x, g_y) $ are cells without icebergs.
• $1 \leq X \leq HW - 2$
• $0 \leq A_{i,j} \leq X$
• $ A_{i,j} $ contains all numbers from $ 1 $ to $ X $.
• $1 \leq C_i \leq 10^{10}$

Partial Points

• Correctly solving all test cases where $H, W \leq 40$ and $X \leq 9$ awards $ 160 $ points.
• Correctly solving all test cases where $H, W \leq 40$ awards an additional $ 400 $ points.
• Correctly solving all test cases awards an additional $ 240 $ points.

Explanation

Explanation

见题面 Input 部分

见题面 Output 部分