Description

« Pour les problèmes que vous ne savez pas résoudre, soumettez simplement quelque chose au hasard. Qui sait, peut-être que ça passera. »

Étant donné une matrice de nombres de taille $n \times m$, vous pouvez réarranger arbitrairement les nombres dans chaque ligne afin que la somme des valeurs minimales de toutes les colonnes soit maximisée.

Formellement, soit $A$ la matrice réarrangée. Maximisez $\sum_{j=1}^m (\min_{i=1}^n A_{i,j})$.

Vous devez afficher cette valeur maximale.

« Le plus souvent, le fait que les choses aillent à l'encontre de nos souhaits est tout simplement la norme dans la vie. »

Entrée

La première ligne de l'entrée contient le nombre de cas de test $T$ ($1 \leq T \leq 10^5$).

Pour chaque cas de test, la première ligne contient deux entiers positifs $n, m$ ($1 \leq n, m \leq 1000$), représentant la taille de la matrice.

Les $n$ lignes suivantes contiennent chacune $m$ entiers, représentant les nombres $A_{i,j}$ dans la matrice ($0 \leq A_{i,j} \leq 10^9$).

Il est garanti que la somme de $n \cdot m$ sur tous les cas de test ne dépasse pas $10^6$.

Sortie

Pour chaque cas de test, affichez un seul entier sur une ligne représentant la réponse.

Exemples

Entrée 1

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

Sortie 1

5
5
4