YiYi 有一个长度为nnn的数组aaa,数组中的数字全是正整数,她希望你使用移动操作帮她把数组排个序,使其单调不减。
在每次移动操作中,你可以:
在你的每次移动过程中,除了你移动的数字,其他位置的数字的相对位置不会改变。
但是,她还给你提出了一个限制,那就是在你移动任何一个数字的前后,有kkk个数字的绝对位置(就是数字在数组中的下标)不能改变。
她想请你帮帮她,计算出把数组排序的最小代价是多少,如果数组在限制条件下没有方法变得单调不减,请输出-1。
-1
第一行,一个整数 t(1≤t≤104)t(1\le t \le 10^4)t(1≤t≤104),代表数据组数。
对于每组数据: 第一行,两个整数 n,k(1≤n≤3⋅105;0≤k≤n)n,k(1\le n \le 3·10^5;0 \le k \le n)n,k(1≤n≤3⋅105;0≤k≤n)代表数组中元素的数量和绝对位置不能改变的数字数量。 第二行,nnn个整数,代表数组 a(1≤ai≤109)a(1\le a_i \le 10^9)a(1≤ai≤109)。 第三行,kkk个整数,每个元素 ban(1≤ban≤n)ban(1\le ban \le n)ban(1≤ban≤n)代表绝对位置不能改变的数字位置,保证每个banbanban互不相同。
保证 ∑n≤3⋅105\sum n \le 3·10^5∑n≤3⋅105。
如果在限制条件下数组最终可以通过操作单调不减,输出排序的最小代价。 否则,输出-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
样例解释: 对于第111组数据,可以按照如下方式移动: 2 1 3 5 4 -> 1 2 3 5 4 -> 1 2 3 4 5 ,即移动数字111和444,代价为 1+4=51+4=51+4=5,且此时数字333的绝对位置均无改变。 对于第333组数据,因为无法移动最后一个444,所以不论怎么移动数字,序列都不可能单调不减。
2 1 3 5 4
1 2 3 5 4
1 2 3 4 5