I. YiYi and Her Unsorted Array

传统 2000 ms 1024 MiB
标准 IO
Special Judge

题目描述

YiYi 有一个长度为nn的数组aa,数组中的数字全是正整数,她希望你使用移动操作帮她把数组排个序,使其单调不减

在每次移动操作中,你可以:

  • 选择数组中某一个位置的数字aia_i,将这个数字移动到数组的其他任意位置,且这次操作的代价就是你移动的数字aia_i的大小。

在你的每次移动过程中,除了你移动的数字,其他位置的数字的相对位置不会改变。

但是,她还给你提出了一个限制,那就是在你移动任何一个数字的前后,有kk个数字的绝对位置(就是数字在数组中的下标)不能改变。

她想请你帮帮她,计算出把数组排序的最小代价是多少,如果数组在限制条件下没有方法变得单调不减,请输出-1

输入格式

第一行,一个整数 t(1t104)t(1\le t \le 10^4),代表数据组数。

对于每组数据:
第一行,两个整数 n,k(1n3105;0kn)n,k(1\le n \le 3·10^5;0 \le k \le n)代表数组中元素的数量和绝对位置不能改变的数字数量。
第二行,nn个整数,代表数组 a(1ai109)a(1\le a_i \le 10^9)
第三行,kk个整数,每个元素 ban(1bann)ban(1\le ban \le n)代表绝对位置不能改变的数字位置,保证每个banban互不相同。

保证 n3105\sum n \le 3·10^5

输出格式

如果在限制条件下数组最终可以通过操作单调不减,输出排序的最小代价。
否则,输出-1

样例

输入样例:

3
5 1
2 1 3 5 4
3
4 0
1 7 3 2

6 2
1 1 4 5 1 4
2 6

输出样例:

5
5
-1

样例解释:
对于第11组数据,可以按照如下方式移动:
2 1 3 5 4 -> 1 2 3 5 4 -> 1 2 3 4 5 ,即移动数字1144,代价为 1+4=51+4=5,且此时数字33的绝对位置均无改变。
对于第33组数据,因为无法移动最后一个44,所以不论怎么移动数字,序列都不可能单调不减。