E - Wish List Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

お店に N 個の商品が並んでおり、それらは商品 1 、商品 2 、\ldots 、商品 N と番号づけられています。
i = 1, 2, \ldots, N について、商品 i の定価は A_i 円です。また、各商品の在庫は 1 つです。

高橋君は、商品 X_1 、商品 X_2 、\ldots 、商品 X_M の M 個の商品が欲しいです。

高橋君は、欲しい商品をすべて手に入れるまで、下記の行動を繰り返します。

現在売れ残っている商品の個数を r とする。 1 \leq j \leq r を満たす整数 j を選び、現在売れ残っている商品のうち番号が j 番目に小さい商品を、その定価に C_j 円だけ加えた金額で購入する。

高橋君が欲しい商品をすべて手に入れるまでにかかる合計費用としてあり得る最小値を出力してください。

なお、高橋君は欲しい商品ではない商品を購入することもできます。

制約

  • 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

高橋君は下記の手順で行動することで、欲しい商品をすべて手に入れるまでにかかる合計費用を最小にすることができます。

  • はじめ、商品 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 円です。これが合計費用としてあり得る最小値です。

入力例 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

Score : 500 points

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