/ 
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 回目の操作で選んだ 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 を出力してください。可能な場合、そのような一連の操作のコストの最小値を出力してください。
入力例 1
4 1 3 3 1 2 4
出力例 1
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 であることが証明できます。
入力例 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