E - Wish List
当前没有测试数据。
E - 愿望清单
得分：500分
问题描述
商店里有$N$个物品，编号为物品1，物品2，...，物品$N$。
对于每个$i = 1, 2, ..., N$，物品$i$的定价是$A_i$日元。对于每个物品，只有一个库存。
高桥想要$M$个物品：物品$X_1$，物品$X_2$，...，物品$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$
- 输入中的所有值都是整数。
输入
输入通过以下格式从标准输入给出：
输出
输出答案。
5 2
3 1 4 1 5
9 2 6 5 3
3 5
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$日元，这是可能的最小费用。
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