← 返回题目列表

AtCoder · agc062_b

B. 拆分并插入

中文机器翻译题面 查看原题

[英文翻译]

分数: 700 点

问题陈述

有一个排列 A=(A_1,A_2,\dots,A_N) 中的整数 1 to N。最初,我们有 A_i=i\ (1\leq i \leq N).

Takahashi 将对此序列执行以下操作 K 次。

  • 选择一个整数 k 这样 0 \leq k < N。拿最后一个 k 条款 A 并将它们插入到第一个 N-k。更准确地说,替换 A 任意排列 A' 的 N 满足以下条件的整数。
    • (A_1,A_2,\dots,A_{N-k}) 是(不一定是连续的)子序列 A'.
    • (A_{N-k+1},A_{N-k+2},\dots,A_{N}) 是(不一定是连续的)子序列 A'.

这一系列操作的成本是 \sum_{i=1}^{K}k_iC_i,其中 k_i 是 k 选择于 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 to 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