Problembeschreibung

Ich bin es leid zu schreiben, ich will nicht mehr schreiben.

„Das nennt man ‚müde‘.“

Gegeben ist eine Folge $a_1,a_2\ldots a_n$ der Länge $n$, wobei jede Position $i$ Änderungskosten $c_i$ hat. Für eine Position kannst du die Kosten $c_i$ bezahlen, um $a_i$ in einen beliebigen Wert zu ändern. Du möchtest die Gesamtkosten minimieren, sodass keine Präfixsumme der Folge durch $r$ teilbar ist.

Formal sei $s_i=\sum_{j=1}^{i}a_j$. Du musst sicherstellen, dass für die modifizierte Folge für alle $1 \le i \le n$ gilt: $s_i \bmod r \ne 0$.

Eingabe

Die erste Zeile enthält die Anzahl der Testfälle $T$ ($1 \le T \le 10^5$).

Für jeden Testfall enthält die erste Zeile zwei positive ganze Zahlen $n,r$ ($1 \le n \le 5\cdot 10^5$, $2 \le r \le 10^9$).

Die nächste Zeile enthält $n$ nichtnegative ganze Zahlen $a_i$ ($0 \le a_i < r$), die die Folge darstellen.

Die nächste Zeile enthält $n$ nichtnegative ganze Zahlen $c_i$ ($0 \le c_i \le 10^9$), die die Änderungskosten darstellen.

Es wird garantiert, dass die Summe aller $n$ den Wert $5\cdot 10^5$ nicht überschreitet.

Ausgabe

Gib für jeden Testfall eine ganze Zahl in einer einzigen Zeile aus, die die minimalen Kosten darstellt.

Beispiele

Eingabe 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

Ausgabe 1

2
3
2
10
2