102884: [AtCoder]ABC288 E - Wish List

Problem Statement

There are $N$ items in a shop, numbered as Item $1$, Item $2$, $\ldots$, Item $N$.
For each $i = 1, 2, \ldots, N$, the regular price of Item $i$ is $A_i$ yen. For each item, there is only one in stock.

Takahashi wants $M$ items: Item $X_1$, Item $X_2$, $\ldots$, Item $X_M$.

He repeats the following until he gets all items he wants.

Let $r$ be the number of unsold items now. Choose an integer $j$ such that $1 \leq j \leq r$, and buy the item with the $j$-th smallest item number among the unsold items, for its regular price plus $C_j$ yen.

Print the smallest total amount of money needed to get all items Takahashi wants.

Takahashi may also buy items other than the ones he wants.

Constraints

• $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$
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

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

Output

Print the answer.

Sample Input 1

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

Sample Output 1

17

Here is a way for Takahashi to get all items he wants with the smallest total amount of money.

• Initially, five items, Items $1, 2, 3, 4, 5$, are remaining. Choose $j = 5$ to buy the item with the fifth smallest item number among the remaining, Item $5$, for $A_5 + C_5 = 5 + 3 = 8$ yen.
• Then, four items, Items $1, 2, 3, 4$, are remaining. Choose $j = 2$ to buy the item with the second smallest item number among the remaining, Item $2$, for $A_2 + C_2 = 1 + 2 = 3$ yen.
• Then, three items, Items $1, 3, 4$, are remaining. Choose $j = 2$ to buy the item with the second smallest item number among the remaining, Item $3$, for $A_3 + C_2 = 4 + 2 = 6$ yen.

Now, Takahashi has all items he wants, Items $3$ and $5$, (along with Item $2$, which is not wanted) for a total cost of $8 + 3 + 6 = 17$ yen, the minimum possible.

Sample Input 2

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

Sample Output 2

533

问题描述

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

对于每件商品$i$，其原价为$A_i$日元。每件商品只有一件库存。

Takahashi想要$M$件商品：Item $X_1$，Item $X_2$，$\ldots$，Item $X_M$。

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

现在有$r$件未售出的商品。 选择一个整数$j$，满足$1 \leq j \leq r$，并以原价加上$C_j$日元的价格购买其中未售出商品中第$j$小编号的商品。

输出得到Takahashi想要的所有商品所需的最小总金额。

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

约束

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

输入

输入数据从标准输入按以下格式给出：

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

输出

输出答案。

样例输入1

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

样例输出1

17

Takahashi可以以最小总金额得到他想要的所有商品的一种方式如下：

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

现在，Takahashi得到了他想要的所有商品，即Item $3$和Item $5$，（以及不想要的Item $2$）的总成本为$8 + 3 + 6 = 17$日元，这是可能的最小值。

样例输入2

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

样例输出2

533