الوصف

«بالنسبة للمسائل التي لا تعرف كيف تحلها، فقط أرسل شيئاً عشوائياً. من يدري، ربما ينجح الأمر.»

تُعطى مصفوفة أعداد بأبعاد $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