心愿清单 - 代码源竞赛平台

题目描述

一家商店有 $N$ 件商品，编号为 $1$ 到 $N$，每件库存只有 $1$ 个。第 $i$ 件商品的原价为 $A_i$。蜗蜗想买到编号为 $X_1,X_2,\ldots,X_M$ 的商品。

每次购买时，先把当前还未售出的商品按编号从小到大排列。若其中共有 $r$ 件，蜗蜗可以选择 $1\le j\le r$，购买排在第 $j$ 位的商品，支付该商品的原价再加 $C_j$ 元。购买后，这件商品从列表中移除，其余商品的名次可能改变。

蜗蜗可以额外购买不在心愿清单上的商品。求买到全部心愿商品需要支付的最少总费用。

输入格式

第一行包含两个整数 $N,M$，表示商品总数和心愿商品数量。

第二行包含 $N$ 个整数 $A_1,A_2,\ldots,A_N$，表示商品原价。

第三行包含 $N$ 个整数 $C_1,C_2,\ldots,C_N$，表示购买当前第 $j$ 位商品时的附加费用。

第四行包含 $M$ 个严格递增的整数 $X_1,X_2,\ldots,X_M$，表示心愿商品编号。

输出格式

输出一行一个整数，表示买到全部心愿商品的最少总费用。

样例

3 1
4 2 6
3 1 5
2

3

2 2
1 2
2 1
1 2

6

样例解释

样例 1 中，商品 $2$ 当前排在第 $2$ 位，直接购买需要 $A_2+C_2=2+1=3$ 元。

样例 2 中，可以先买编号 $2$ 的商品，花费 $A_2+C_2=3$ 元；此时只剩编号 $1$ 的商品，买它再花费 $A_1+C_1=3$ 元，总计 $6$ 元。

数据范围

对于 100% 的数据，保证 $1\le M\le N\le 5000$，$1\le A_i,C_i\le 10^9$，$1\le X_1<X_2<\cdots<X_M\le N$。