B - Split and Insert Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 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' の(連続とは限らない)部分列である。

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


入力例 1

4 1
3
3 1 2 4

出力例 1

6

操作で k=2 とし、A_3=3A_1,A_2 より前に、 A_4=4A_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

[English Translation]

Score : 700 points

Problem Statement

There is a permutation A=(A_1,A_2,\dots,A_N) of the integers from 1 to N. Initially, we have A_i=i\ (1\leq i \leq N).

Takahashi will perform the following operation on this sequence K times.

  • Choose an integer k such that 0 \leq k < N. Take the last k terms of A and insert them among the first N-k. More precisely, replace A with any permutation A' of the N integers that satisfies the following conditions.
    • (A_1,A_2,\dots,A_{N-k}) is a (not necessarily contiguous) subsequence of A'.
    • (A_{N-k+1},A_{N-k+2},\dots,A_{N}) is a (not necessarily contiguous) subsequence of A'.

The cost of the series of operations is \sum_{i=1}^{K}k_iC_i, where k_i is the k chosen in the i-th operation.

Takahashi wants to perform K operations so that A=(P_1,P_2,\dots,P_N) afterward.

Determine whether it is possible to perform such a series of operations. If it is possible, find its minimum cost.

Constraints

  • 2 \leq N \leq 100
  • 1 \leq K \leq 100
  • 1 \leq C_i \leq 10^9
  • (P_1,P_2,\dots,P_N) is a permutation of the integers from 1 to N.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N K
C_1 C_2 \dots C_K
P_1 P_2 \dots P_N

Output

If it is impossible to perform K operations so that A=(P_1,P_2,\dots,P_N) holds afterward, print -1. If it is possible, print the minimum cost of such a series of operations.


Sample Input 1

4 1
3
3 1 2 4

Sample Output 1

6

By choosing k=2, and inserting A_3=3 before A_1,A_2 and A_4=4 after A_1,A_2, we can make A=(3,1,2,4), which satisfies A=(P_1,P_2,P_3,P_4). The cost of this operation is 2 \times C_1 = 6.

It can be proved that the minimum cost of performing operations so that A=(P_1,P_2,P_3,P_4) afterward is 6.


Sample Input 2

4 1
3
4 3 2 1

Sample Output 2

-1

It is impossible to perform operations so that A=(P_1,P_2,P_3,P_4) afterward.


Sample Input 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

Sample Output 3

7372920743