11241번 - Hive 다국어

문제

กาลครั้งหนึ่งมีทุ่งดอกไม้สีชมพูแห่งหนึ่งขนาด N x M ตารางเมตร ในแต่ละตารางเมตรมีดอกไม้อยู่ a_ij ดอก ทุกๆเช้าฝูงกระต่ายจะมาเก็บดอกไม้เหล่านี้กลับไปกินเพื่อให้ขนของพวกมันมีสีชมพู โดยกระต่ายแต่ละตัวจะเดินจากซ้ายบน ไปขวาล่าง และจะไม่เดินกลับไปทางด้านซ้ายหรือกลับขึ้นด้านบนเด็ดขาด ส าหรับทุกๆตารางเมตรที่เดินผ่านและยังมีดอกไม้อยู่กระต่ายจะเก็บดอกไม้ 1 ดอก ถามว่าต้องใช้กระต่ายอย่างน้อยกี่ตัวจึงจะเก็บดอกไม้ได้ทั้งหมด

입력

บรรทัดแรกเป็นจ านวนกรณีทดสอบ T ชุด (1 ≤ T ≤ 10) กรณีทดสอบแต่ชุดประกอบด้วยข้อมูลดังนี้

• บรรทัดแรก เป็นจ านวนแถวและคอลัมน์ของทุ่งหญ้า N และ M ตามล าดับ (1 < N, M ≤ 1 600)
• บรรทัดที่ 2 ถึง N+1 ประกอบด้วยจ านวนเต็ม M จ านวน โดยแต่ละจ านวน a_ij แสดงจ านวน ดอกไม้ในตารางเมตรนั้น (0 ≤ a_ij ≤ 100)

출력

ส าหรับแต่ละกรณีทดสอบ ให้แสดงจ านวนกระต่ายที่น้อยที่สุดที่ใช้ในการเก็บดอกไม้ทั้งหมด

제한

힌트