分数: 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