問題文

魔法少女のjoisinoお姉ちゃんは、この世にあるすべての数字を $1$ に変えてやろうと思い立ちました。

$1$ つの数字を $i$ から $j(0≦i,j≦9)$ に書き変えるには魔力 $c_{i,j}$ が必要です。

今、目の前にある壁は縦方向に $H$、横方向に $W$ のマス目になっていて、$1$ つ以上のマス目に $0$ 以上 $9$ 以下の整数が $1$ つずつ書かれています。

上から $i(1≦i≦H)$ 番目、左から $j(1≦j≦W)$ 番目のマスの情報として $A_{i,j}$ が与えられ、

• $A_{i,j}≠-1$ の場合はマスに $A_{i,j}$ が書かれている
• $A_{i,j}=-1$ の場合はマスに数字が書かれていない

ことを意味します。

この壁に書かれている数字を最終的に全て $1$ に変えるのに必要な魔力の最小量を求めてください。

制約

• $1≦H,W≦200$
• $1≦c_{i,j}≦10^3 (i≠j)$
• $c_{i,j}=0 (i=j)$
• $\-1≦A_{i,j}≦9$
• 入力は整数からなる
• 壁には一つ以上の整数が書かれている

入力

入力は以下の形式で標準入力から与えられる。

$H$ $W$ $c_{0,0}$ $...$ $c_{0,9}$ $:$ $c_{9,0}$ $...$ $c_{9,9}$ $A_{1,1}$ $...$ $A_{1,W}$ $:$ $A_{H,1}$ $...$ $A_{H,W}$

出力

壁に書かれている数字を最終的に全て $1$ に変えるのに必要な魔力の最小量を出力せよ。

入力例 1

2 4
0 9 9 9 9 9 9 9 9 9
9 0 9 9 9 9 9 9 9 9
9 9 0 9 9 9 9 9 9 9
9 9 9 0 9 9 9 9 9 9
9 9 9 9 0 9 9 9 9 2
9 9 9 9 9 0 9 9 9 9
9 9 9 9 9 9 0 9 9 9
9 9 9 9 9 9 9 0 9 9
9 9 9 9 2 9 9 9 0 9
9 2 9 9 9 9 9 9 9 0
-1 -1 -1 -1
8 1 1 8

出力例 1

12

$8$ を $1$ に変えるとき、 $8$ を $4$ に変え、その後 $4$ を $9$ に、$9$ を $1$ に変えると必要な魔力が最小となります。

壁には $8$ が $2$ つ書かれているので、必要な魔力の最小量は $6×2=12$です。

入力例 2

5 5
0 999 999 999 999 999 999 999 999 999
999 0 999 999 999 999 999 999 999 999
999 999 0 999 999 999 999 999 999 999
999 999 999 0 999 999 999 999 999 999
999 999 999 999 0 999 999 999 999 999
999 999 999 999 999 0 999 999 999 999
999 999 999 999 999 999 0 999 999 999
999 999 999 999 999 999 999 0 999 999
999 999 999 999 999 999 999 999 0 999
999 999 999 999 999 999 999 999 999 0
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

出力例 2

0

壁に書かれている数字を全く変える必要がない場合に注意してください。

入力例 3

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

出力例 3

47