Опис

«Для задач, які не знаєш як розв'язати, просто відправ щось випадкове. Хто знає, раптом пройде».

Дано матрицю чисел розміру $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