Deskripsi

"Untuk soal yang tidak tahu cara menyelesaikannya, kirimkan saja sesuatu secara acak. Siapa tahu, mungkin saja akan lolos."

Diberikan sebuah matriks angka berukuran $n \times m$, Anda boleh menyusun ulang angka-angka pada setiap baris secara bebas sehingga jumlah dari nilai minimum di semua kolom menjadi maksimum.

Secara formal, misalkan matriks yang telah disusun ulang adalah $A$. Maksimalkan $\sum_{j=1}^m (\min_{i=1}^n A_{i,j})$.

Anda perlu mengeluarkan nilai maksimum ini.

"Lebih sering daripada tidak, segala sesuatu yang berjalan tidak sesuai keinginan kita hanyalah hal yang lumrah dalam hidup."

Masukan

Baris pertama masukan berisi banyaknya kasus uji $T$ ($1 \leq T \leq 10^5$).

Untuk setiap kasus uji, baris pertama berisi dua bilangan bulat positif $n, m$ ($1 \leq n, m \leq 1000$), yang menyatakan ukuran matriks.

$n$ baris berikutnya masing-masing berisi $m$ bilangan bulat, yang menyatakan angka-angka $A_{i,j}$ di dalam matriks ($0 \leq A_{i,j} \leq 10^9$).

Dijamin bahwa jumlah dari $n \cdot m$ di seluruh kasus uji tidak melebihi $10^6$.

Keluaran

Untuk setiap kasus uji, keluarkan sebuah bilangan bulat pada satu baris yang menyatakan jawabannya.

Contoh

Masukan 1

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

Keluaran 1

5
5
4