لديك تبديل $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$ مباشرة، بإنفاق قطعة نقدية واحدة.

في حالة الاختبار الثالثة، أحد تسلسلات العمليات المثلى هو التالي:

• أعد ترتيب العناصر الموجودة في مواضع اللون $2$ للحصول على التبديل $(5,2,4,3,1,6)$. تكلف هذه العملية قطعة نقدية واحدة.
• بدّل العنصرين $p_3,p_4$. يصبح التبديل $(5,2,3,4,1,6)$. تكلف هذه العملية 10 قطع نقدية.
• أعد ترتيب العناصر الموجودة في مواضع اللون $1$ للحصول على التبديل $(1,2,3,4,5,6)$. تكلف هذه العملية قطعة نقدية واحدة.

أنفقنا في المجموع 12 قطعة نقدية.

في حالة الاختبار الرابعة، التبديل مرتب أصلًا، لذا لا نحتاج إلى إنفاق أي شيء.