題目描述

我寫到攰喇，唔想再寫落去喇。

「呢啲就叫做『攰喇』。」

俾定一個長度為 $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