愿望清单

题目描述

商店里有 $N$ 件商品,编号为商品 $1$,商品 $2$,$\ldots$,商品 $N$。

对每个 $i = 1, 2, \ldots, N$,商品 $i$ 的标价为 $A_i$ 日元。每种商品均只有 1 件库存。

高桥想要 $M$ 件商品:商品 $X_1$,商品 $X_2$,$\ldots$,商品 $X_M$。

他重复以下操作,直到买到所有想要的商品。

设当前未售出的商品数为 $r$。选择满足 $1 \leq j \leq r$ 的整数 $j$,以标价加上 $C_j$ 日元的价格,购买未售出商品中编号第 $j$ 小的商品。

输出高桥买到所有想要的商品所需的最小总金额。

高桥也可以购买他不想要的商品。

输入格式

输入按以下格式从标准输入给出:

$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$,以 $A_5 + C_5 = 5 + 3 = 8$ 日元购买剩余商品中编号第 5 小的商品,即商品 $5$。

然后,还剩商品 $1, 2, 3, 4$ 共 4 件。选择 $j = 2$,以 $A_2 + C_2 = 1 + 2 = 3$ 日元购买剩余商品中编号第 2 小的商品,即商品 $2$。

然后,还剩商品 $1, 3, 4$ 共 3 件。选择 $j = 2$,以 $A_3 + C_2 = 4 + 2 = 6$ 日元购买剩余商品中编号第 2 小的商品,即商品 $3$。

此时高桥已买到所有想要的商品(商品 $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

数据范围

• $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$
• 输入中的所有值均为整数。