يمتلك 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$.