[英文翻译]
分数: 700 点
问题陈述
有一个排列 A=(A_1,A_2,\dots,A_N) 中的整数 1 to N。最初,我们有 A_i=i\ (1\leq i \leq N).
Takahashi 将对此序列执行以下操作 K 次。
- 选择一个整数 k 这样 0 \leq k < N。拿最后一个 k 条款 A 并将它们插入到第一个 N-k。更准确地说,替换 A 任意排列 A' 的 N 满足以下条件的整数。
- (A_1,A_2,\dots,A_{N-k}) 是(不一定是连续的)子序列 A'.
- (A_{N-k+1},A_{N-k+2},\dots,A_{N}) 是(不一定是连续的)子序列 A'.
这一系列操作的成本是 \sum_{i=1}^{K}k_iC_i,其中 k_i 是 k 选择于 i第次操作。
高桥想要表演 K 操作使得 A=(P_1,P_2,\dots,P_N) 之后。
判断是否可以执行这样一系列的操作。如果可能的话,求其最小成本。
约束
- 2 \leq N \leq 100
- 1 \leq K \leq 100
- 1 \leq C_i \leq 10^9
- (P_1,P_2,\dots,P_N) 是以下整数的排列 1 to N.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N K C_1 C_2 \dots C_K P_1 P_2 \dots P_N
输出
如果无法执行 K 操作使得 A=(P_1,P_2,\dots,P_N) 之后保存,打印 -1。如果可以的话,打印出这样一系列操作的最小成本。
示例输入 1
4 1 3 3 1 2 4
示例输出 1
6
通过选择 k=2,并插入 A_3=3 之前 A_1,A_2 和 A_4=4 之后 A_1,A_2,我们可以制作 A=(3,1,2,4),满足 A=(P_1,P_2,P_3,P_4)。该操作的成本是 2 \times C_1 = 6.
可以证明执行操作的最小成本使得 A=(P_1,P_2,P_3,P_4) 之后是 6.
示例输入 2
4 1 3 4 3 2 1
示例输出 2
-1
无法执行以下操作 A=(P_1,P_2,P_3,P_4) 之后。
示例输入 3
20 10 874735445 684260477 689935252 116941558 915603029 923404262 843759669 656978932 286318130 255195090 11 15 20 10 6 8 18 2 12 4 9 13 19 3 16 7 14 17 5 1
示例输出 3
7372920743