Farmer John は船で Cowribbean Sea の $N$ 個の島 $(1 \le N \le 100)$ の一つにある伝説の宝を探します。番号は $1,\ldots,N$ です。

地図は1から始め $N$ で終わり、$M$ 個の島 $(2 \le M \le 10,000)$ の列 $A_{1}$、$A_{2}$、……、$A_{M}$ を通れば宝が現れると示します。これらや他の島を別順や繰り返し訪ねてもよいですが、指定順の $A_{i}$ を含む必要があります。

FJ は海賊を避けたく、各島対の危険度 $(0 \le danger \le 100,000)$ を知っています。総危険度は通る全経路の危険度の和です。

地図条件を満たす宝への最小危険経路を求めてください。

入力

• 1行目：空白区切りの2整数 $N$ と $M$。
• $2,\ldots,M+1$ 行目：$i+1$ 行目は必訪の $i_{th}$ 番目の島の整数 $A_{i}$。
• $M+2,\ldots,N+M+1$ 行目：$i+M+1$ 行目は空白区切り $N$ 整数で、島 $i$ から1、2、……、$N$ への危険度です。$i$ 番目は必ず0。

出力

• 1行目：宝を得る最小危険度。

入出力例

入力 1

3 4
1
2
1
3
0 5 1
5 0 2
1 2 0

出力 1

7

注記

3島で訪問4島の順は1、2、再び1、最後3。経路(1,2)、(2,3)、(3,1)と逆向きは危険5、2、1です。

1、3、2、3、1、3で総危険7、条件の1、2、1、3を満たします。危険の高い1–2を避けます。

問題作成者：Jeffrey Wang, 2007