配点 : $700$ 点

問題文

$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'$ の（連続とは限らない）部分列である。
• $(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)$ が成り立つように操作を行いたいです。

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

制約

• $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 を出力してください。可能な場合、そのような一連の操作のコストの最小値を出力してください。

4 1
3
3 1 2 4

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

4 1
3
4 3 2 1

-1

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

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