序列

题目描述

给定一个长度为 $n$ 的序列 $a_1,a_2,\dots,a_n$。每个位置 $i$ 有一个修改代价 $c_i$：对于任意一个位置，你可以花费代价 $c_i$，将该位置的 $a_i$ 修改为任意一个非负整数。

你希望花费最小的总代价进行若干次修改，使得修改后的序列满足：每一个前缀和都不是 $r$ 的倍数。

形式化地，令 $s_i=\sum_{j=1}^{i}a_j$。你需要保证修改后的序列对所有 $1\le i\le n$ 都有 $s_i \bmod r \ne 0$。

求最小的总代价。

输入格式

第一行一个整数 $T$（$1\le T\le 10^5$），表示测试数据组数。

对于每组测试数据：

• 第一行两个正整数 $n,r$（$1\le n\le 5\cdot 10^5$，$2\le r\le 10^9$）。
• 第二行 $n$ 个非负整数 $a_1,a_2,\dots,a_n$（$0\le a_i<r$），表示原序列。
• 第三行 $n$ 个非负整数 $c_1,c_2,\dots,c_n$（$0\le c_i\le 10^9$），表示每个位置的修改代价。

保证所有测试数据的 $\sum n$ 不超过 $5\cdot 10^5$。

输出格式

对于每组测试数据，输出一行一个整数，表示最小总代价。

样例 #1

样例输入 #1

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

样例输出 #1

1
0
3

样例 #1 解释

• 第一组：初始前缀和为 $1,3,0\pmod 7$，第三个前缀和是 $7$ 的倍数。将 $a_3$ 改为 $3$（花费 $c_3=1$），前缀和变为 $1,3,6$，均不为 $7$ 的倍数，代价为 $1$。
• 第二组：前缀和为 $1,2,3,4$，均不为 $5$ 的倍数，无需修改，代价为 $0$。
• 第三组：$r=2$，需保证每个前缀和都是奇数。可依次将 $a_1$ 改为 $1$、$a_2$ 改为 $0$、$a_4$ 改为 $0$，代价为 $1+1+1=3$。

数据范围与子任务

对于所有数据：$1\le n\le 5\cdot 10^5$，$2\le r\le 10^9$，$0\le a_i<r$，$0\le c_i\le 10^9$，$\sum n\le 5\cdot 10^5$。