กำหนดการเรียงสับเปลี่ยน $p_1,p_2,\ldots,p_n$ ของจำนวนเต็มตั้งแต่ $1$ ถึง $n$ แต่ละตำแหน่งตั้งแต่ $1$ ถึง $n$ ถูกระบายด้วยสีหนึ่งใน $k$ สี เราต้องการเรียงลำดับการเรียงสับเปลี่ยนนี้ และสามารถทำการดำเนินการต่อไปนี้ได้กี่ครั้งก็ได้:

• สลับสมาชิกสองตัวใด ๆ การดำเนินการนี้ใช้เงิน $S$ เหรียญ;
• เลือกสี $i$ ใด ๆ แล้วจัดเรียงสมาชิกที่อยู่ในตำแหน่งสี $i$ ใหม่ได้ตามต้องการ การดำเนินการนี้ใช้เงิน $C_i$ เหรียญ

สังเกตว่าสิ่งที่ถูกระบายสีคือตำแหน่ง ไม่ใช่สมาชิก ดังนั้นเมื่อสลับสมาชิกสองตัว สีของตำแหน่งจะไม่เปลี่ยน

จงหาจำนวนเหรียญน้อยที่สุดที่ต้องใช้เพื่อเรียงลำดับการเรียงสับเปลี่ยน

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

บรรทัดแรกมีจำนวนเต็มหนึ่งจำนวน $T$ ($1\le T\le10^3$) แทนจำนวนกรณีทดสอบอิสระที่ต้องประมวลผล จากนั้นเป็นรายละเอียดของกรณีทดสอบ

บรรทัดแรกของแต่ละกรณีมีจำนวนเต็มสองจำนวน $n,k$ ($1\le n\le10^5$, $1\le k\le5$) แทนขนาดของการเรียงสับเปลี่ยนและจำนวนสี

บรรทัดที่สองของแต่ละกรณีมีจำนวนเต็ม $k+1$ จำนวน $S,C_1,C_2,\ldots,C_k$ ($0\le S,C_i\le10^9$) แทนค่าใช้จ่ายของการดำเนินการ

บรรทัดที่สามของแต่ละกรณีมีจำนวนเต็ม $n$ จำนวน $p_1,p_2,\ldots,p_n$ ($1\le p_i\le n$ และ $p_i$ ทุกตัวแตกต่างกัน) แทนการเรียงสับเปลี่ยน

บรรทัดที่สี่ของแต่ละกรณีมีจำนวนเต็ม $n$ จำนวน $col_i$ ($1\le col_i\le k$) แทนสีของแต่ละตำแหน่ง

ผลรวมของ $n$ ในทุกกรณีทดสอบของหนึ่งไฟล์ไม่เกิน $10^5$

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

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

ตัวอย่าง

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

4
4 1
1 10
2 3 4 1
1 1 1 1
4 1
10 1
2 3 4 1
1 1 1 1
6 2
10 1 1
5 2 4 6 1 3
1 2 1 2 1 2
4 3
6 7 8 9
1 2 3 4
2 2 3 2

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

3
1
12
0

หมายเหตุ

ในกรณีทดสอบแรก เราสามารถเรียงลำดับการเรียงสับเปลี่ยนได้ด้วยการสลับ 3 ครั้ง: $(2,3,4,1)\to(4,3,2,1)\to(4,2,3,1)\to(1,2,3,4)$ วิธีนี้ใช้เงิน 3 เหรียญ

อีกวิธีคือจัดเรียงสมาชิกทั้งหมดในตำแหน่งสี $1$ ใหม่ แต่วิธีนั้นใช้เงิน 10 เหรียญ และเราสามารถทำได้ถูกกว่านั้น

อย่างไรก็ตาม ในกรณีทดสอบที่สอง ซึ่งแตกต่างจากกรณีแรกเฉพาะค่าใช้จ่ายของการดำเนินการ การจัดเรียงสมาชิกทั้งหมดในตำแหน่งสี $1$ ใหม่โดยใช้เงิน 1 เหรียญนั้นถูกกว่า

ในกรณีทดสอบที่สาม หนึ่งในลำดับการดำเนินการที่เหมาะที่สุดคือ:

• จัดเรียงสมาชิกในตำแหน่งสี $2$ ใหม่ เพื่อให้ได้การเรียงสับเปลี่ยน $(5,2,4,3,1,6)$ การดำเนินการนี้ใช้เงิน 1 เหรียญ
• สลับสมาชิก $p_3,p_4$ การเรียงสับเปลี่ยนตอนนี้คือ $(5,2,3,4,1,6)$ การดำเนินการนี้ใช้เงิน 10 เหรียญ
• จัดเรียงสมาชิกในตำแหน่งสี $1$ ใหม่ เพื่อให้ได้การเรียงสับเปลี่ยน $(1,2,3,4,5,6)$ การดำเนินการนี้ใช้เงิน 1 เหรียญ

รวมแล้วเราใช้เงิน 12 เหรียญ

ในกรณีทดสอบที่สี่ การเรียงสับเปลี่ยนเรียงลำดับอยู่แล้ว จึงไม่ต้องใช้เงินเลย