คำอธิบายโจทย์

"สำหรับโจทย์ที่คุณไม่รู้วิธีแก้ ก็แค่ส่งอะไรสุ่มๆ ไป ใครจะรู้ล่ะ บางทีมันอาจจะผ่านก็ได้"

กำหนดเมทริกซ์ของตัวเลขขนาด $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