Mô tả bài toán

"Đối với những bài bạn không biết làm, cứ nộp đại một thứ ngẫu nhiên nào đó. Biết đâu đấy, có khi lại qua."

Cho một ma trận số kích thước $n \times m$, bạn có thể sắp xếp lại tùy ý các số trong mỗi hàng sao cho tổng các giá trị nhỏ nhất của tất cả các cột đạt giá trị lớn nhất.

Một cách hình thức, gọi ma trận sau khi sắp xếp lại là $A$. Hãy cực đại hóa $\sum_{j=1}^m (\min_{i=1}^n A_{i,j})$.

Bạn cần in ra giá trị lớn nhất này.

"Phần lớn thời gian, việc mọi thứ đi ngược lại mong muốn của chúng ta đơn giản chỉ là lẽ thường tình trong cuộc sống."

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa số lượng bộ dữ liệu $T$ ($1 \leq T \leq 10^5$).

Đối với mỗi bộ dữ liệu, dòng đầu tiên chứa hai số nguyên dương $n, m$ ($1 \leq n, m \leq 1000$), biểu thị kích thước của ma trận.

$n$ dòng tiếp theo, mỗi dòng chứa $m$ số nguyên, biểu thị các số $A_{i,j}$ trong ma trận ($0 \leq A_{i,j} \leq 10^9$).

Dữ liệu đảm bảo tổng của $n \cdot m$ trên tất cả các bộ dữ liệu không vượt quá $10^6$.

Kết quả

Đối với mỗi bộ dữ liệu, in ra một số nguyên duy nhất trên một dòng biểu thị câu trả lời.

Ví dụ

Dữ liệu vào 1

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

Kết quả 1

5
5
4