Problembeskrivning

Jag är trött på att skriva, jag vill inte skriva mer.

"Det här kallas att vara 'trött'."

Givet en talföljd $a_1,a_2\ldots a_n$ av längd $n$, har varje position $i$ en ändringskostnad $c_i$. För en position kan du betala kostnaden $c_i$ för att ändra $a_i$ till vilket värde som helst. Du vill minimera den totala kostnaden så att ingen prefixsumma i talföljden är delbar med $r$.

Formellt, låt $s_i=\sum_{j=1}^{i}a_j$. Du måste se till att det för den modifierade talföljden gäller för alla $1 \le i \le n$ att $s_i \bmod r \ne 0$.

Indata

Den första raden innehåller antalet testfall $T$ ($1 \le T \le 10^5$).

För varje testfall innehåller den första raden två positiva heltal $n,r$ ($1 \le n \le 5\cdot 10^5$, $2 \le r \le 10^9$).

Nästa rad innehåller $n$ icke-negativa heltal $a_i$ ($0 \le a_i < r$), som representerar talföljden.

Nästa rad innehåller $n$ icke-negativa heltal $c_i$ ($0 \le c_i \le 10^9$), som representerar ändringskostnaderna.

Det garanteras att summan av alla $n$ inte överstiger $5\cdot 10^5$.

Utdata

För varje testfall, skriv ut ett heltal på en egen rad som representerar den minimala kostnaden.

Exempel

Indata 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

Utdata 1

2
3
2
10
2