시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 10 | 5 | 3 | 50.000% |
กาลครั้งหนึ่งมีทุ่งดอกไม้สีชมพูแห่งหนึ่งขนาด N x M ตารางเมตร ในแต่ละตารางเมตรมีดอกไม้อยู่ aij ดอก ทุกๆเช้าฝูงกระต่ายจะมาเก็บดอกไม้เหล่านี้กลับไปกินเพื่อให้ขนของพวกมันมีสีชมพู โดยกระต่ายแต่ละตัวจะเดินจากซ้ายบน ไปขวาล่าง และจะไม่เดินกลับไปทางด้านซ้ายหรือกลับขึ้นด้านบนเด็ดขาด ส าหรับทุกๆตารางเมตรที่เดินผ่านและยังมีดอกไม้อยู่กระต่ายจะเก็บดอกไม้ 1 ดอก ถามว่าต้องใช้กระต่ายอย่างน้อยกี่ตัวจึงจะเก็บดอกไม้ได้ทั้งหมด
บรรทัดแรกเป็นจ านวนกรณีทดสอบ T ชุด (1 ≤ T ≤ 10) กรณีทดสอบแต่ชุดประกอบด้วยข้อมูลดังนี้
ส าหรับแต่ละกรณีทดสอบ ให้แสดงจ านวนกระต่ายที่น้อยที่สุดที่ใช้ในการเก็บดอกไม้ทั้งหมด
3 3 4 4 4 0 0 0 4 4 0 0 0 4 4 2 4 0 0 0 4 4 0 0 0 4 4 2 3 1 4 4 3 2 1 2 3 4 1 2 1 4 3
4 8 11