题目描述

お店に $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$ 円だけ加えた金額で購入する。

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

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

输入格式

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

$N$ $M$ $A_1$ $A_2$ $\ldots$ $A_N$ $C_1$ $C_2$ $\ldots$ $C_N$ $X_1$ $X_2$ $\ldots$ $X_M$

输出格式

答えを出力せよ。

题目大意

题目描述

商店里有 $N$ 件商品，标号 $1\sim N$，第 $i$ 件商品有底价 $A_i$ 且只有一件。

Takahashi 想要买其中的 $M$ 件商品，分别是标号 $X_1,X_2,\ldots,X_M$ 的商品。

他会按照以下的方式买东西：

若还剩 $r$ 件商品没有购买过，选择一个符合 $1\le j\le r$ 的 $j$，付这件商品的底价加上 $C_j$ 的钱购买其中标号第 $j$ 小的商品。

求出买到它想要的商品所付的最小价钱。

注意他也可以买不想要的商品。

输入格式

第一行两个正整数 $N$ 和 $M$（$1\le M\le N\le 5000$）表示物品数量和想要的物品数量。

第二行 $n$ 个正整数表示 $A$ 数组（$1\le A_i\le 10^9$）。

第三行 $n$ 个正整数表示 $C$ 数组（$1\le C_i\le 10^9$）。

第四行 $m$ 个正整数表示 $X$ 数组（$1\le X_1 < X_2 < \ldots < X_M\le N$）。

输出格式

一行一个正整数表示答案。

样例解释

样例 $1$ 中，下面是一种可行的方法：

• 一开始有标号为 $1,2,3,4,5$ 的物品。选择 $j = 5$，购买标号第 $5$ 小的物品（即物品 $5$），付 $A_5 + C_5 = 8$ 的钱；

• 此时有标号为 $1,2,3,4$ 的物品。选择 $j = 2$，购买标号第 $2$ 小的物品（即物品 $2$），付 $A_2 + C_2 = 3$ 的钱；

• 最后有标号为 $1,3,4$ 的物品。选择 $j = 2$，购买标号第 $2$ 小的物品（即物品 $3$），付 $A_3 + C_2 = 6$ 的钱。

Takahashi 现在买到了想要的物品（$3$ 和 $5$）以及一个不想要的物品 $2$，付了最少的 $8+3+6 = 17$ 的钱。

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

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

提示

制約

• $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$
• 入力はすべて整数

Sample Explanation 1

高橋君は下記の手順で行動することで、欲しい商品をすべて手に入れるまでにかかる合計費用を最小にすることができます。 - はじめ、商品 $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$ 円です。これが合計費用としてあり得る最小値です。