Opis

„W przypadku zadań, których nie potrafisz rozwiązać, po prostu wyślij coś losowego. Kto wie, może przejdzie”.

Dana jest macierz liczb o wymiarach $n \times m$. Możesz dowolnie przestawiać liczby w każdym wierszu tak, aby suma minimalnych wartości ze wszystkich kolumn była jak największa.

Formalnie, niech macierz po przestawieniu oznacza $A$. Zmaksymalizuj $\sum_{j=1}^m (\min_{i=1}^n A_{i,j})$.

Musisz wypisać tę maksymalną wartość.

„Częściej niż rzadziej to, że sprawy idą wbrew naszym życzeniom, jest po prostu życiową normą”.

Wejście

Pierwszy wiersz wejścia zawiera liczbę przypadków testowych $T$ ($1 \leq T \leq 10^5$).

Dla każdego przypadku testowego pierwszy wiersz zawiera dwie dodatnie liczby całkowite $n, m$ ($1 \leq n, m \leq 1000$), oznaczające wymiary macierzy.

Kolejne $n$ wierszy zawiera po $m$ liczb całkowitych, oznaczających liczby $A_{i,j}$ w macierzy ($0 \leq A_{i,j} \leq 10^9$).

Gwarantuje się, że suma $n \cdot m$ po wszystkich przypadkach testowych nie przekracza $10^6$.

Wyjście

Dla każdego przypadku testowego wypisz w osobnym wierszu jedną liczbę całkowitą oznaczającą odpowiedź.

Przykłady

Wejście 1

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

Wyjście 1

5
5
4