题目描述

有一个由 $1$ 到 $N$ 的整数构成的排列 $A=(A_1,A_2,\dots,A_N)$。初始时 $A_i=i\ (1\leq i \leq N)$。

高桥君对这个排列进行如下操作 $K$ 次：

• 选择一个满足 $0\leq k < N$ 的整数 $k$。将 $A$ 的最后 $k$ 项插入到前 $N-k$ 项中。更准确地说，将 $A$ 替换为任意满足以下条件的长度为 $N$ 的排列 $A'$：
  • $(A_1,A_2,\dots,A_{N-k})$ 是 $A'$ 的（不一定连续的）子序列。
  • $(A_{N-k+1},A_{N-k+2},\dots,A_{N})$ 是 $A'$ 的（不一定连续的）子序列。

第 $i$ 次操作选择的 $k$ 为 $k_i$ 时，这一系列操作的总代价为 $\sum_{i=1}^{K}k_iC_i$。

高桥君希望经过 $K$ 次操作后，使 $A=(P_1,P_2,\dots,P_N)$ 成立。

请判断是否存在这样的操作序列。如果存在，求出使 $A=(P_1,P_2,\dots,P_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。
如果可以，请输出使 $A=(P_1,P_2,\dots,P_N)$ 的最小总代价。

样例 1

输入

4 1
3
3 1 2 4

输出

6

样例 2

输入

4 1
3
4 3 2 1

输出

-1

样例 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

输出

7372920743

说明/提示

限制条件

• $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$ 的一个排列
• 输入的所有值均为整数

样例解释 1

操作时选择 $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

无法通过操作使 $A=(P_1,P_2,P_3,P_4)$ 成立。

由 ChatGPT 4.1 翻译