配点 : $500$ 点

問題文

お店に $N$ 個の商品が並んでおり、それらは商品 $1$ 、商品 $2$ 、$\ldots$ 、商品 $N$ と番号づけられています。 $i = 1, 2, \ldots, N$ について、商品 $i$ の定価は $A_i$ 円です。また、各商品の在庫は $1$ つです。

高橋君は、商品 $X_1$ 、商品 $X_2$ 、$\ldots$ 、商品 $X_M$ の $M$ 個の商品が欲しいです。

高橋君は、欲しい商品をすべて手に入れるまで、下記の行動を繰り返します。

現在売れ残っている商品の個数を $r$ とする。 $1 \leq j \leq r$ を満たす整数 $j$ を選び、現在売れ残っている商品のうち番号が $j$ 番目に小さい商品を、その定価に $C_j$ 円だけ加えた金額で購入する。

高橋君が欲しい商品をすべて手に入れるまでにかかる合計費用としてあり得る最小値を出力してください。

なお、高橋君は欲しい商品ではない商品を購入することもできます。

制約

• $1 \leq M \leq N \leq 5000$
• $1 \leq A_i \leq 10^9$
• $1 \leq C_i \leq 10^9$
• $1 \leq X_1 \lt X_2 \lt \cdots \lt X_M \leq N$
• 入力はすべて整数

入力

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

$N$ $M$

$A_1$ $A_2$ $\ldots$ $A_N$

$C_1$ $C_2$ $\ldots$ $C_N$

$X_1$ $X_2$ $\ldots$ $X_M$

出力

答えを出力せよ。

5 2
3 1 4 1 5
9 2 6 5 3
3 5

17

高橋君は下記の手順で行動することで、欲しい商品をすべて手に入れるまでにかかる合計費用を最小にすることができます。

• はじめ、商品 $1, 2, 3, 4, 5$ の $5$ 個の商品が売れ残っています。 高橋君は $j = 5$ を選び、売れ残っている商品のうち番号が $5$ 番目に小さい商品 $5$ を、$A_5 + C_5 = 5 + 3 = 8$ 円で購入します。
• その後、商品 $1, 2, 3, 4$ の $4$ 個の商品が売れ残っています。 高橋君は $j = 2$ を選び、売れ残っている商品のうち番号が $2$ 番目に小さい商品 $2$ を、$A_2 + C_2 = 1 + 2 = 3$ 円で購入します。
• その後、商品 $1, 3, 4$ の $3$ 個の商品が売れ残っています。 高橋君は $j = 2$ を選び、売れ残っている商品のうち番号が $2$ 番目に小さい商品 $3$ を、$A_3 + C_2 = 4 + 2 = 6$ 円で購入します。

以上の手順によって、高橋君は欲しい商品である商品 $3, 5$ のすべて（および、欲しい商品ではない商品 $2$ ）を手に入れることができ、 それまでにかかる合計費用は $8 + 3 + 6 = 17$ 円です。これが合計費用としてあり得る最小値です。

20 8
29 27 79 27 30 4 93 89 44 88 70 75 96 3 78 39 97 12 53 62
32 38 84 49 93 53 26 13 25 2 76 32 42 34 18 77 14 67 88 12
1 3 4 5 8 14 16 20

533