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