題目描述

「對於你不會做的題目，隨便交點隨機的東西上去。誰知道呢，說不定就過了。」

給定一個 $n \times m$ 的數字矩陣，你可以任意重新排列每一列中的數字，使得所有行的最小值之和最大。

正式地，設重排後的矩陣為 $A$。最大化 $\sum_{j=1}^m (\min_{i=1}^n A_{i,j})$。

你需要輸出這個最大值。

「很多時候，事與願違只是生活中的常態。」

輸入格式

輸入的第一行包含測試資料的數量 $T$（$1 \leq T \leq 10^5$）。

對於每組測試資料，第一行包含兩個正整數 $n, m$（$1 \leq n, m \leq 1000$），表示矩陣的大小。

接下來的 $n$ 行，每行包含 $m$ 個整數，表示矩陣中的數字 $A_{i,j}$（$0 \leq A_{i,j} \leq 10^9$）。

保證所有測試資料的 $n \cdot m$ 之和不超過 $10^6$。

輸出格式

對於每組測試資料，在單獨的一行中輸出一個整數，表示答案。

範例

範例輸入 1

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

範例輸出 1

5
5
4