问题描述

南極海是一个 $H \times W$ 的网格。从海洋上的第 $i$ 行第 $j$ 列开始，用 $(i, j)$ 来表示该位置。

南極海中有许多冰山。探险家小蓝想要从起点 $(s_x, s_y)$ 移动到终点 $(g_x, g_y)$，每次只能向上下左右相邻的方格移动。由于无法移动到有冰山的方格上，可能需要融化一些冰山。

每个冰山都有一个融化的代价 $C_k$。 要到达 $(g_x, g_y)$ 的最小代价是多少？

共有 $X$ 个冰山。方格 $(i, j)$ 的状态是 $A_{i,j}$。当 $A_{i,j} = 0$ 时，表示该方格没有冰山。 当 $1 \leq A_{i,j} \leq X$ 时，表示该方格有冰山 $A_{i,j}$。注意，具有相同编号的冰山方格在上下左右是连通的。

约束条件

• 输入都是整数
• $1 \leq H, W \leq 500$
• $1 \leq s_x, g_x \leq H$
• $1 \leq s_y, g_y \leq W$
• $(s_x, s_y), (g_x, g_y)$ 都不是冰山方格
• $1 \leq X \leq HW - 2$
• $0 \leq A_{i,j} \leq X$
• $A_{i,j}$ 中包含了 $1, 2, 3, \dots, X$
• $1 \leq C_i \leq 10^{10}$

部分得分

• 当 $H, W \leq 40, X \leq 9$ 时，全部正确可得到 160 分。
• 当 $H, W \leq 40$ 时，全部正确可得到额外的 400 分。
• 全部正确可得到额外的 240 分。

输入

输入以以下格式从标准输入中给出。

$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$

输出

输出探险家小蓝到达终点的最小代价。

示例 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

输出示例 1

13

示例 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

输出示例 2

1211

解释

解答