Mô tả bài toán

Tôi viết mệt rồi, tôi không muốn viết thêm nữa.

"Đó gọi là 'mệt mỏi'."

Cho một dãy $a_1,a_2\ldots a_n$ có độ dài $n$, mỗi vị trí $i$ có chi phí sửa đổi là $c_i$. Đối với một vị trí, bạn có thể trả chi phí $c_i$ để đổi $a_i$ thành bất kỳ giá trị nào. Bạn muốn cực tiểu hóa tổng chi phí sao cho mọi tổng tiền tố của dãy đều không chia hết cho $r$.

Một cách hình thức, đặt $s_i=\sum_{j=1}^{i}a_j$. Bạn cần đảm bảo rằng đối với dãy sau khi sửa đổi, với mọi $1 \le i \le n$, $s_i \bmod r \ne 0$.

Dữ liệu vào

Dòng đầu tiên chứa số lượng bộ dữ liệu $T$ ($1 \le T \le 10^5$).

Với mỗi bộ dữ liệu, dòng đầu tiên chứa hai số nguyên dương $n,r$ ($1 \le n \le 5\cdot 10^5$, $2 \le r \le 10^9$).

Dòng tiếp theo chứa $n$ số nguyên không âm $a_i$ ($0 \le a_i < r$), biểu diễn dãy số.

Dòng tiếp theo chứa $n$ số nguyên không âm $c_i$ ($0 \le c_i \le 10^9$), biểu diễn chi phí sửa đổi.

Dữ liệu đảm bảo tổng của tất cả các $n$ không vượt quá $5\cdot 10^5$.

Kết quả

Với mỗi bộ dữ liệu, in ra một số nguyên trên một dòng duy nhất, biểu thị chi phí nhỏ nhất.

Ví dụ

Dữ liệu vào 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

Kết quả 1

2
3
2
10
2