[英文翻译]

题目描述

有一个 $1$ 到 $N$ 的整数序列的排列 $A=(A_1,A_2,\\dots,A_N)$。最初，我们有 $A_i=i\\ (1\\leq i \\leq N)$。

高桥会对这个序列进行以下操作 $K$ 次。

• 选择一个整数 $k$ 满足 $0 \\leq k < N$。将 $A$ 的最后 $k$ 个项插入到前面的 $N-k$ 个项中。更准确地说，用满足以下条件的任意排列 $A'$ 替换 $A$。
  • $(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$ 是第 $i$ 次操作选择的 $k$。

高桥希望执行 $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$ 到 $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