題目描述

我寫累了，我不想再寫了。

「這就叫『累了』。」

給定一個長度為 $n$ 的序列 $a_1,a_2\ldots 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_i$ ($0 \le a_i < r$)，表示該序列。

再下一行包含 $n$ 個非負整數 $c_i$ ($0 \le c_i \le 10^9$)，表示修改代價。

保證所有 $n$ 的總和不超過 $5\cdot 10^5$。

輸出格式

對於每組測試資料，在一行中輸出一個整數，表示最小代價。

範例

範例輸入 1

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

範例輸出 1

2
3
2
10
2