Kuvaus

”Tehtäviin, joita et osaa ratkaista, lähetä vain jotain satunnaista. Kuka tietää, ehkä se menee läpi.”

Annettuna on $n \times m$ -kokoinen lukumatriisi. Voit järjestää kunkin rivin luvut mielivaltaisesti uudelleen siten, että kaikkien sarakkeiden minimiarvojen summa maksimoituu.

Muodollisesti, olkoon uudelleenjärjestetty matriisi $A$. Maksimoi $\sum_{j=1}^m (\min_{i=1}^n A_{i,j})$.

Sinun tulee tulostaa tämä suurin arvo.

”Useimmiten se, että asiat menevät toiveidemme vastaisesti, on yksinkertaisesti elämän normi.”

Syöte

Syötteen ensimmäinen rivi sisältää testitapausten lukumäärän $T$ ($1 \leq T \leq 10^5$).

Jokaisessa testitapauksessa ensimmäinen rivi sisältää kaksi positiivista kokonaislukua $n, m$ ($1 \leq n, m \leq 1000$), jotka kuvaavat matriisin kokoa.

Seuraavat $n$ riviä sisältävät kukin $m$ kokonaislukua, jotka kuvaavat matriisin lukuja $A_{i,j}$ ($0 \leq A_{i,j} \leq 10^9$).

On taattu, että tulojen $n \cdot m$ summa yli kaikkien testitapausten ei ylitä arvoa $10^6$.

Tuloste

Tulosta jokaiselle testitapaukselle omalle rivilleen yksi kokonaisluku, joka kuvaa vastausta.

Esimerkit

Syöte 1

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

Tuloste 1

5
5
4