配点: $800$ 点

問題文

南極海は、$H \\times W$ のマス目で表されます。海の上から $i$ マス目、左から $j$ マス目の部分を $(i, j)$ で表します。

南極海には多くの氷山があります。探検家のいろはちゃんは、$(s_x, s_y)$ から $(g_x, g_y)$ まで、上下左右に隣り合ったマス目への移動を繰り返して移動したいです。氷山があるマス目に移動することはできないので、いくつかの氷山を融かす必要があるかもしれません。

それぞれの氷山には融かすためのコストが決まっています。$k$ 個目の氷山をすべて融かすためのコストは $C_k$ 円です。 いろはちゃんが $(s_x, s_y)$ から $(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$ (2019/05/01 13:45 追記)
• $1 \\leq s_y, g_y \\leq W$ (2019/05/01 13:45 追記)
• $(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

解説

解説