VegiCat-тың $k$ бос емес командаға бөлінген $n$ қызметкері бар компаниясы бар. Қызметкерлер сан осі ретінде берілген түзу жолдың бойында тұрады. VegiCat олар үшін екі кездесу орнын ұйымдастырғысы келеді.

VegiCat командаларды әр команда дәл бір жиынға тиесілі болатындай етіп $A$ және $B$ екі жиынына бөледі. Ол әр жиын үшін кез келген нақты координатадан бір кездесу орнын таңдайды. Бір командадағы барлық қызметкерлер бір кездесу орнына баруы керек. $A$ жиынындағы әр команда $A$ үшін таңдалған кездесу орнына, ал $B$ жиынындағы әр команда $B$ үшін таңдалған кездесу орнына барады. Жиындардың кез келгені бос болуы мүмкін.

$S_A$ арқылы $A$ жиынындағы командалардың барлық қызметкерлерінің үй орналасу тізімін белгілейік, ал $B$ үшін $S_B$ тізімін дәл солай анықтайық. Үйлердің орналасуы қайталанса да, әр қызметкер бөлек есептеледі.

Үй орналасуларының $S = (x_1, x_2, \ldots, x_m)$ тізімі үшін осы қызметкерлердің бір кездесу орнына жетуіне қажетті ең аз жалпы қашықтық:

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

$S$ бос болғанда $M(S) = 0$ деп анықтайық. Командаларды екі жиынға бөлудің барлық тәсілдері бойынша $M(S_A) + M(S_B)$ мәнін барынша азайтуға VegiCat-қа көмектесіңіз.

Кіріс деректер

Бірінші жолда тесттер санын білдіретін бір бүтін сан $T$ ($1 \le T \le 3 \cdot 10^5$) берілген. Одан кейін тесттердің сипаттамасы беріледі.

Әр тесттің бірінші жолында қызметкерлер санын және командалар санын білдіретін екі бүтін сан $n$ мен $k$ ($1 \le k \le n \le 3 \cdot 10^5$) берілген.

Келесі $k$ жолдың әрқайсысы бір команданы сипаттайды. $i$-ші жолда $i$-ші командадағы қызметкерлер санын білдіретін бүтін сан $m_i$ ($1 \le m_i \le n$), ал одан кейін олардың үйлерінің орналасуын білдіретін $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$ болады.