Beskrivelse

«For oppgaver du ikke vet hvordan du skal løse, bare send inn noe tilfeldig. Hvem vet, kanskje det går gjennom.»

Gitt en $n \times m$-matrise med tall, kan du vilkårlig omorganisere tallene i hver rad slik at summen av minimumsverdiene i alle kolonnene maksimeres.

Formelt, la den omorganiserte matrisen være $A$. Maksimer $\sum_{j=1}^m (\min_{i=1}^n A_{i,j})$.

Du må skrive ut denne maksimale verdien.

«Som oftest er det at ting går imot ønskene våre rett og slett normen i livet.»

Inndata

Den første linjen i inndata inneholder antallet testtilfeller $T$ ($1 \leq T \leq 10^5$).

For hvert testtilfelle inneholder den første linjen to positive heltall $n, m$ ($1 \leq n, m \leq 1000$), som representerer størrelsen på matrisen.

De neste $n$ linjene inneholder hver $m$ heltall, som representerer tallene $A_{i,j}$ i matrisen ($0 \leq A_{i,j} \leq 10^9$).

Det garanteres at summen av $n \cdot m$ over alle testtilfeller ikke overstiger $10^6$.

Utdata

For hvert testtilfelle skal du skrive ut ett enkelt heltall på én linje som representerer svaret.

Eksempler

Inndata 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