Problembeskrivelse

Jeg er lei av å skrive, jeg vil ikke skrive mer.

«Dette kalles å være 'sliten'.»

Gitt en følge $a_1,a_2\ldots a_n$ med lengde $n$, har hver posisjon $i$ en endringskostnad $c_i$. For en posisjon kan du betale kostnaden $c_i$ for å endre $a_i$ til en hvilken som helst verdi. Du ønsker å minimere den totale kostnaden slik at ingen prefikssum av følgen er delelig med $r$.

Formelt, la $s_i=\sum_{j=1}^{i}a_j$. Du må sørge for at det for den endrede følgen, for alle $1 \le i \le n$, gjelder at $s_i \bmod r \ne 0$.

Inndata

Den første linjen inneholder antall testtilfeller $T$ ($1 \le T \le 10^5$).

For hvert testtilfelle inneholder den første linjen to positive heltall $n,r$ ($1 \le n \le 5\cdot 10^5$, $2 \le r \le 10^9$).

Den neste linjen inneholder $n$ ikke-negative heltall $a_i$ ($0 \le a_i < r$), som representerer følgen.

Den neste linjen inneholder $n$ ikke-negative heltall $c_i$ ($0 \le c_i \le 10^9$), som representerer endringskostnadene.

Det er garantert at summen av alle $n$ ikke overstiger $5\cdot 10^5$.

Utdata

For hvert testtilfelle, skriv ut ett heltall på en enkelt linje, som representerer den minimale kostnaden.

Eksempler

Inndata 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