題目描述

「對於你唔識做嘅題目，隨便交啲隨機嘅嘢上去。邊個知呢，話唔定就過咗。」

俾定一個 $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