Wish List

题目描述

商店里有 $N$ 件商品，编号为 Item $1$, Item $2$, $\ldots$, Item $N$.
对于每个 $i = 1, 2, \ldots, N$，第 $i$ 件商品的标价为 $A_i$ 日元。每件商品仅有一件库存。 Takahashi 想要 $M$ 件商品：Item $X_1$, Item $X_2$, $\ldots$, Item $X_M$。 他重复以下操作直到得到所有想要的商品为止。

设 $r$ 为当前尚未售出的商品数量。 选择一个整数 $j$，使得 $1 \leq j \leq r$，并以该时刻未售出商品中第 $j$ 小的商品编号对应的商品的标价加上 $C_j$ 日元的价格购买该商品。

输出得到 Takahashi 想要的所有商品所需的最小总金额。 Takahashi 也可以购买他不想要的商品。

输入格式

输入从标准输入给出，格式如下： $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

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$ 输入中的所有数值均为整数。下面给出一种使 Takahashi 以最小总金额得到他想要的所有商品的方法。

最初，五件商品 Items $1, 2, 3, 4, 5$ 仍在。 选择 $j = 5$ 以购买当前剩余商品中第 5 小编号的商品，即 Item $5$，价格为 $A_5 + C_5 = 5 + 3 = 8$ 日元。 然后，还剩四件商品 Items $1, 2, 3, 4$。 选择 $j = 2$ 以购买当前剩余商品中第 2 小编号的商品，即 Item $2$，价格为 $A_2 + C_2 = 1 + 2 = 3$ 日元。 然后，还剩三件商品 Items $1, 3, 4$。 选择 $j = 2$ 以购买当前剩余商品中第 2 小编号的商品，即 Item $3$，价格为 $A_3 + C_2 = 4 + 2 = 6$ 日元。

现在，Takahashi 已得到他想要的所有商品 Items $3$ 和 $5$，（以及一件不想要的商品 Item $2$），总花费为 $8 + 3 + 6 = 17$ 日元，这也是最小可能的。

标签: AtCoder|abc288E

来源

AtCoder|abc288E