คำอธิบายโจทย์

ฉันเหนื่อยที่จะเขียนแล้ว ฉันไม่อยากเขียนอีกต่อไป

"นี่แหละที่เรียกว่า 'เหนื่อย'"

กำหนดลำดับ $a_1,a_2\ldots a_n$ ที่มีความยาว $n$ โดยแต่ละตำแหน่ง $i$ มีค่าใช้จ่ายในการแก้ไขเป็น $c_i$ สำหรับตำแหน่งหนึ่งๆ คุณสามารถจ่ายค่าใช้จ่าย $c_i$ เพื่อเปลี่ยน $a_i$ ให้เป็นค่าใดก็ได้ คุณต้องการทำให้ค่าใช้จ่ายรวมน้อยที่สุด โดยที่ผลรวมนำหน้าทุกตัวของลำดับจะต้องไม่หารด้วย $r$ ลงตัว

กล่าวอย่างเป็นทางการ ให้ $s_i=\sum_{j=1}^{i}a_j$ คุณต้องทำให้แน่ใจว่าสำหรับลำดับที่ถูกแก้ไขแล้ว สำหรับทุกๆ $1 \le i \le n$ จะต้องได้ $s_i \bmod r \ne 0$

ข้อมูลนำเข้า

บรรทัดแรกประกอบด้วยจำนวนกรณีทดสอบ $T$ ($1 \le T \le 10^5$)

สำหรับแต่ละกรณีทดสอบ บรรทัดแรกประกอบด้วยจำนวนเต็มบวกสองจำนวน $n,r$ ($1 \le n \le 5\cdot 10^5$, $2 \le r \le 10^9$)

บรรทัดถัดไปประกอบด้วยจำนวนเต็มไม่ลบ $n$ จำนวน คือ $a_i$ ($0 \le a_i < r$) แทนลำดับ

บรรทัดถัดไปประกอบด้วยจำนวนเต็มไม่ลบ $n$ จำนวน คือ $c_i$ ($0 \le c_i \le 10^9$) แทนค่าใช้จ่ายในการแก้ไข

รับประกันว่าผลรวมของ $n$ ทั้งหมดไม่เกิน $5\cdot 10^5$

ข้อมูลส่งออก

สำหรับแต่ละกรณีทดสอบ ให้พิมพ์จำนวนเต็มหนึ่งตัวในหนึ่งบรรทัด แทนค่าใช้จ่ายที่น้อยที่สุด

ตัวอย่าง

ข้อมูลนำเข้า 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

ข้อมูลส่งออก 1

2
3
2
10
2