Deskripsi Masalah

Aku lelah menulis, aku tidak ingin menulis lagi.

"Ini yang disebut 'lelah'."

Diberikan sebuah barisan $a_1,a_2\ldots a_n$ dengan panjang $n$, setiap posisi $i$ memiliki biaya modifikasi $c_i$. Untuk suatu posisi, Anda dapat membayar biaya $c_i$ untuk mengubah $a_i$ menjadi nilai apa pun. Anda ingin meminimalkan total biaya sehingga setiap jumlah prefiks dari barisan tersebut tidak habis dibagi oleh $r$.

Secara formal, misalkan $s_i=\sum_{j=1}^{i}a_j$. Anda perlu memastikan bahwa untuk barisan yang telah dimodifikasi, untuk semua $1 \le i \le n$, berlaku $s_i \bmod r \ne 0$.

Format Masukan

Baris pertama berisi banyaknya kasus uji $T$ ($1 \le T \le 10^5$).

Untuk setiap kasus uji, baris pertama berisi dua bilangan bulat positif $n,r$ ($1 \le n \le 5\cdot 10^5$, $2 \le r \le 10^9$).

Baris berikutnya berisi $n$ bilangan bulat tak negatif $a_i$ ($0 \le a_i < r$), yang menyatakan barisan tersebut.

Baris berikutnya berisi $n$ bilangan bulat tak negatif $c_i$ ($0 \le c_i \le 10^9$), yang menyatakan biaya modifikasi.

Dijamin bahwa jumlah dari semua $n$ tidak melebihi $5\cdot 10^5$.

Format Keluaran

Untuk setiap kasus uji, keluarkan satu bilangan bulat dalam satu baris, yang menyatakan biaya minimum.

Contoh

Masukan 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

Keluaran 1

2
3
2
10
2