题目描述

$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)$ が成り立つように操作を行いたいです。

そのように一連の操作を行うことが可能か判定してください。可能な場合、そのような一連の操作にかかるコストの最小値を求めてください。

输入格式

入力は以下の形式で標準入力から与えられます。

$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=(A_1,A_2,\dots,A_N)$ 。一开始，排列满足 $A_i=i\ (1\leq i \leq N)$。接下来高桥会进行 $K$ 次操作，操作如下：

• 任意选择一个 $k$ ，选择排列最末尾 $k$ 个元素，将其插入进前面 $n-k$ 个元素。形式化的，操作之后的排列需要满足：
• 1. $(A_1,A_2,\dots,A_{N-k})$ 是一个操作后排列子序列（不要求连续）
  2. $(A_{N-k+1},A_{N-k+2},\dots,A_{N})$ 是操作后排列的一个子序列（不要求连续）

定义所有操作的代价是 $\sum_{i=1}^{K}k_iC_i$，其中 $k_i$ 表示第 $i$ 轮选择的 $k$ 。

现在高桥君想问你能否在 $K$ 次以内将排列变为 $(P_1,P_2,\dots,P_N)$，如果可以输出最小代价，如果不能输出 $-1$ 。

4 1
3
3 1 2 4

6

4 1
3
4 3 2 1

-1

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$ までの整数からなる順列
• 入力される値はすべて整数

Sample Explanation 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$ であることが証明できます。

Sample Explanation 2

操作後、$A=(P_1,P_2,P_3,P_4)$ が成り立つように操作することはできません。