Lýsing

„Fyrir dæmi sem þú veist ekki hvernig á að leysa skaltu bara senda inn eitthvað af handahófi. Hver veit, kannski nær það í gegn.“

Gefin er $n \times m$ fylki af tölum. Þú mátt endurraða tölunum í hverri röð aðildarlaust þannig að summa lággilda allra dálka verði sem mest.

Formlega, látum endurraðaða fylkið vera $A$. Hámarkaðu $\sum_{j=1}^m (\min_{i=1}^n A_{i,j})$.

Þú þarft að prenta þetta hámarksgildi.

„Oftar en ekki er það einfaldlega gangur lífsins að hlutirnir fari á skjön við óskir okkar.“

Inntak

Fyrsta línan í inntakinu inniheldur fjölda prófunartilfella $T$ ($1 \leq T \leq 10^5$).

Fyrir hvert prófunartilfelli inniheldur fyrsta línan tvær jákvæðar heiltölur $n, m$ ($1 \leq n, m \leq 1000$), sem tákna stærð fylkisins.

Næstu $n$ línur innihalda hver um sig $m$ heiltölur, sem tákna tölurnar $A_{i,j}$ í fylkinu ($0 \leq A_{i,j} \leq 10^9$).

Tryggt er að summa $n \cdot m$ yfir öll prófunartilfelli fari ekki yfir $10^6$.

Úttak

Fyrir hvert prófunartilfelli skal prenta eina heiltölu á einni línu sem táknar svarið.

Dæmi

Inntak 1

3
1 1
5
2 2
1 4
2 5
3 3
1 2 1
2 2 1
1 1 2

Úttak 1

5
5
4