AT_abc288_e [ABC288E] Wish List

商店里有 $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$ 的钱。

### 制約 - $ 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 $ 円です。これが合計費用としてあり得る最小値です。