题面 样例

题目描述

有一个长度为 $n$ 的序列 $p_1,p_2,...,p_n$，满足 $p_i=i$。你需要依次进行 $k$ 次操作，每次操作形如：

选择一个参数 $x\in [0,n)$，将 $p$ 的最后 $x$ 个元素取出，将这 $x$ 个元素重新插入到前 $n-x$ 个元素中。插入的位置可以不连续，但是必须保证这 $x$ 个元素的相对顺序不变。例如 $p=\{1,2,3,4,5\},x=2$，则可能的操作结束后的序列有 $\{4,1,2,5,3\},\{1,2,4,5,3\},\{1,4,2,3,5\},\{1,2,3,4,5\}$ 等。

设 $k$ 次操作选择的参数为 $x_1,x_2,..,x_k$。则操作总代价为 $\sum_{i=1}^{k}c_ix_i$。

现在给出一个序列 $q_1,q_2,...,q_n$。问能否将 $p$ 通过上述的 $k$ 次操作变化为 $q$。若能，则需要求出最小的操作代价。

输入格式

从 ins.in 中读入。

第一行两个正整数 $n,k$。

第二行 $k$ 个正整数 $c_1,c_2,...,c_k$。

第三行 $n$ 个正整数 $q_1,q_2,...,q_n$。

输出格式

输出到 ins.out 中。

如果无解输出 -1；否则输出最小操作代价。

样例输入 1

4 1
3
3 1 2 4

样例输出 1

6

数据范围

对于所有数据，保证 $2\le n\le 100,1\le k\le 100,1\le c_i\le 10^9$ 且 $q_i$ 是 $1\sim n$ 的排列。

对于测试点 $1\sim 2$，满足 $n,k\le 5$。

对于测试点 $3\sim 4$，满足 $k=1$。

对于测试点 $5\sim 6$，满足 $n,k\le 20$。

对于测试点 $7\sim 8$，满足 $n,k\le 50$。

对于测试点 $9\sim 10$，无特殊约束。