SP17396 DCEPC12D - Dazzling Pearls

Nancy 和 Pranjali 是一对好朋友。在 Nancy 生日的时候，Pranjali 送了她一条由 $N$ 颗不同颜色的珍珠制成的美丽手链。虽然被这份心意打动且珍珠美丽异常，Nancy 仍觉得可以稍微改变珍珠的排列，让手链变得更加迷人。经过一番深思熟虑，她想出了一个计算手链优雅因子（E）的公式。 首先，她从某颗珍珠开始，把珍珠编号为 $0$ 到 $N-1$。然后，她根据每颗珍珠的颜色为其分配一个数字值，这样手链就可以用一个大小为 $N$ 的环形整数数组 $A$ 来表示。同时，还有一个数组 $B$，它的大小同样是 $N$。优雅因子 $E$ 通过以下公式计算： $$ E = \sum_{i=1}^{n-1} (A[i] - A[i-1]) \times B[i] $$ Nancy 希望找到一个使得 $E$ 最大化的珍珠排列方式。如果有多个排列能达到这个最大值，她想要字典序最小的那个。 找到理想的排列后，Nancy 准备重新排列手链上的珍珠。然而，她的朋友 Pranjali 不愿意让她对这份礼物改动太多，为了增加难度，她给了 Nancy 一个数字 $D$，并规定一次只能交换两颗相隔 $D$ 的珍珠。 Nancy 不想让朋友失望，同时她也希望能尽快完成排列任务。你能帮助她找出实现这种排列所需的最少移动次数吗？如果无法实现，请输出 -1。 注意： 1. 如果有多种排列可达到最大优雅因子，目标排列总是字典序最小的那个。 2. 手链上最多有 3 种不同颜色的珍珠。 3. 请记住，手链是环形的，距离 $D$ 可以双向计算。

第一行包含整数 $T$，表示测试用例的数量。 每个测试用例第一行包含两个用空格分开的整数 $N$ 和 $D$。 第二行包含 $N$ 个用空格分开的整数，表示数组 $A$。 第三行包含 $N$ 个用空格分开的整数，表示数组 $B$。

输出现成品所需的最少移动次数，如果无法实现，则输出 -1。

- $1 \leq T \leq 100$ - $3 \leq N \leq 10^5$ - $1 \leq D < N$ - $0 \leq A[i], B[i] \leq 10^9$ **本翻译由 AI 自动生成**