בבעלותו של VegiCat חברה עם $n$ עובדים המחולקים ל-$k$ צוותים לא ריקים. העובדים גרים לאורך כביש ישר המיוצג על ידי ציר המספרים. VegiCat רוצה לארגן עבורם שתי נקודות מפגש.

VegiCat מחלק את הצוותים לשתי קבוצות, $A$ ו-$B$, כך שכל צוות נמצא בדיוק בקבוצה אחת. הוא בוחר נקודת מפגש לכל קבוצה בקואורדינטה ממשית כלשהי. כל העובדים באותו צוות חייבים להגיע לאותה נקודת מפגש. כל צוות בקבוצה $A$ הולך לנקודת המפגש של $A$, וכל צוות בקבוצה $B$ הולך לנקודת המפגש של $B$. כל אחת מהקבוצות עשויה להיות ריקה.

תהא $S_A$ רשימת מיקומי הבתים של כל העובדים בצוותים שב-$A$, ונגדיר את $S_B$ באופן דומה עבור $B$. כל עובד נספר בנפרד, גם כאשר מיקומי הבתים חוזרים על עצמם.

עבור רשימה $S = (x_1, x_2, \ldots, x_m)$ של מיקומי בתים, המרחק הכולל המינימלי שעל עובדים אלה לעבור כדי להגיע לנקודת מפגש אחת הוא

$$M(S) = \min_{p \in \mathbb{R}} \sum_{j=1}^{m} |x_j - p|.$$

נגדיר $M(S) = 0$ כאשר $S$ ריקה. עזרו ל-VegiCat למזער את $M(S_A) + M(S_B)$ על פני כל הדרכים לחלק את הצוותים לשתי הקבוצות.

קלט

השורה הראשונה מכילה מספר שלם $T$ ($1 \le T \le 3 \cdot 10^5$), מספר מקרי הבדיקה. אחריה מופיע תיאור מקרי הבדיקה.

השורה הראשונה של כל מקרה בדיקה מכילה שני מספרים שלמים $n$ ו-$k$ ($1 \le k \le n \le 3 \cdot 10^5$), המציינים את מספר העובדים ואת מספר הצוותים, בהתאמה.

כל אחת מ-$k$ השורות הבאות מתארת צוות אחד. השורה ה-$i$ מכילה מספר שלם $m_i$ ($1 \le m_i \le n$), מספר העובדים בצוות $i$, ואחריו $m_i$ מספרים שלמים $x_{i,1}, \ldots, x_{i,m_i}$ ($1 \le x_{i,j} \le 10^7$), מיקומי הבתים שלהם. סכום כל ה-$m_i$ במקרה בדיקה הוא $n$.

מיקומי הבתים עשויים לחזור על עצמם ויכולים להינתן בכל סדר.

מובטח כי סכום ערכי $n$ על פני כל מקרי הבדיקה אינו עולה על $3 \cdot 10^5$.

פלט

עבור כל מקרה בדיקה, הדפיסו מספר שלם — מרחק הנסיעה הכולל המינימלי האפשרי.

דוגמאות

קלט 1

2
4 2
2 1 3
2 8 10
8 3
3 4 12 1
2 3 2
3 9 8 10

פלט 1

4
15

הערה

במקרה הבדיקה הראשון, VegiCat שולח את צוות $1$ לנקודת מפגש במיקום $1$ ואת צוות $2$ לנקודת מפגש במיקום $8$. העובדים בכל צוות עוברים מרחק כולל של $2$, מה שנותן את התשובה $4$.

במקרה הבדיקה השני, VegiCat בוחר נקודות מפגש ב-$3$ וב-$9$. הוא שולח את צוותים $1$ ו-$2$ לנקודת המפגש הראשונה, ואת צוות $3$ לשנייה. העובדים בצוותים $1$, $2$ ו-$3$ עוברים מרחקים כוללים של $12$, $1$ ו-$2$ בהתאמה, מה שנותן את התשובה $15$.