Сипаттамасы

«Шығару жолын білмейтін есептерге жай ғана кездейсоқ бірдеңе жібере салыңыз. Кім біледі, мүмкін өтіп кетер.»

Сандардан тұратын $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$ жолдың әрқайсысында матрицадағы $A_{i,j}$ сандарын білдіретін $m$ бүтін сан берілген ($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