← 返回题目列表

AtCoder · abc288_e

H. 愿望清单

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

有 N 商品,编号为 Item 1, 项目 2, \ldots, 项目 N.
对于每个 i = 1, 2, \ldots, N, 正常价格 项目的 项目数量 i is A_i 日元。对于每件商品,只有一件库存。

高桥想要 M 项目: 项目 X_1, 项目 X_2, \ldots, 项目 X_M.

他重复以下操作,直到获得他想要的所有物品。

让 r 是现在未售出商品的数量。 选择一个整数 j 这样 1 \leq j \leq r,并购买带有 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,剩余。 选择 j = 5 购买剩余商品中商品编号第五小的商品,商品 5,对于 A_5 + C_5 = 5 + 3 = 8 日元。
  • 然后,四个项目,项目 1, 2, 3, 4,剩余。 选择 j = 2 购买剩余商品中商品编号第二小的商品,商品 2,对于 A_2 + C_2 = 1 + 2 = 3 日元。
  • 然后,三个项目,项目 1, 3, 4,剩余。 选择 j = 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