נתונה תמורה $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 מטבעות.

במקרה הבדיקה הרביעי התמורה כבר ממוינת, ולכן אין צורך להוציא דבר.