Описание

«По задачам, которые не знаешь как решать, просто сдай что-нибудь случайное. Кто знает, вдруг пройдёт».

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