Beskrivning

"För problem du inte vet hur man löser, skicka bara in något slumpmässigt. Vem vet, det kanske går igenom."

Givet en $n \times m$-matris av tal får du godtyckligt ordna om talen i varje rad så att summan av minimivärdena i alla kolumner maximeras.

Formellt, låt den omordnade matrisen vara $A$. Maximera $\sum_{j=1}^m (\min_{i=1}^n A_{i,j})$.

Du ska skriva ut detta maximala värde.

"Oftast är det helt enkelt normen i livet att saker och ting går emot våra önskningar."

Indata

Den första raden i indata innehåller antalet testfall $T$ ($1 \leq T \leq 10^5$).

För varje testfall innehåller den första raden två positiva heltal $n, m$ ($1 \leq n, m \leq 1000$), som representerar matrisens storlek.

De följande $n$ raderna innehåller var och en $m$ heltal, som representerar talen $A_{i,j}$ i matrisen ($0 \leq A_{i,j} \leq 10^9$).

Det garanteras att summan av $n \cdot m$ över alla testfall inte överstiger $10^6$.

Utdata

För varje testfall, skriv ut ett enda heltal på en rad som representerar svaret.

Exempel

Indata 1

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

Utdata 1

5
5
4