Beschreibung

„Für Probleme, die man nicht zu lösen weiß, reicht man einfach irgendetwas Zufälliges ein. Wer weiß, vielleicht kommt es ja durch.“

Gegeben ist eine $n \times m$-Zahlenmatrix. Sie dürfen die Zahlen in jeder Zeile beliebig umordnen, sodass die Summe der Minimalwerte aller Spalten maximiert wird.

Formal sei $A$ die umgeordnete Matrix. Maximieren Sie $\sum_{j=1}^m (\min_{i=1}^n A_{i,j})$.

Sie müssen diesen Maximalwert ausgeben.

„Meistens ist es im Leben schlicht die Norm, dass die Dinge unseren Wünschen zuwiderlaufen.“

Eingabe

Die erste Zeile der Eingabe enthält die Anzahl der Testfälle $T$ ($1 \leq T \leq 10^5$).

Für jeden Testfall enthält die erste Zeile zwei positive ganze Zahlen $n, m$ ($1 \leq n, m \leq 1000$), die die Größe der Matrix angeben.

Die nächsten $n$ Zeilen enthalten jeweils $m$ ganze Zahlen, die die Zahlen $A_{i,j}$ in der Matrix darstellen ($0 \leq A_{i,j} \leq 10^9$).

Es wird garantiert, dass die Summe von $n \cdot m$ über alle Testfälle $10^6$ nicht überschreitet.

Ausgabe

Geben Sie für jeden Testfall eine einzige ganze Zahl in einer Zeile aus, die die Antwort darstellt.

Beispiele

Eingabe 1

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

Ausgabe 1

5
5
4