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$