ร้านคอมพิวเตอร์ K.I.B. ต้องการขยายฐานลูกค้าไปยังเมืองใหม่ โดยเมืองดังกล่าวมีการวางผังเมืองเป็นพื้นที่สี่เหลี่ยมย่อยจำนวน MxN พื้นที่ (M แถว N หลัก) และจากการสำรวจสำมะโนประชากรทำให้ทราบจำนวนประชากรในแต่ละพื้นที่ (ดูภาพประกอบด้านล่าง)

เนื่องจากร้าน K.I.B. ต้องการเปิดศูนย์บริการลูกค้าเพียงร้านเดียวในเมืองนี้ ยิ่งไปกว่านั้นพื้นที่บริการที่ร้านให้บริการลูกค้าได้จะครอบคลุมบริเวณที่ประกอบด้วยสี่เหลี่ยมย่อยจำนวน KxK พื้นที่ (K แถว K หลัก) เท่านั้น ทางร้านจึงพยายามหาพื้นที่บริการที่ดีที่สุด ซึ่งในที่นี้หมายถึงพื้นที่บริการที่มีประชากรรวมกันมากที่สุด

ภาพประกอบตัวอย่างโจทย์ แสดงผลการหาทำเลตั้งศูนย์บริการลูกค้าในพื้นที่ขนาด 2x2  (K = 2) ของผังเมืองขนาด 5x10 ในที่นี้บริเวณที่ถูกเน้นคือพื้นที่บริการที่ดีที่สุด

จงเขียนโปรแกรมที่มีประสิทธิภาพในการหาจำนวนประชากรรวมในทำเลพื้นที่บริการที่ดีที่สุด

ข้อมูลนำเข้า

1.       บรรทัดแรกเป็นเลขจำนวนเต็มบวกสองตัวบอกจำนวนแถว (M) และจำนวนหลัก (N) ตามลำดับ โดยที่ 2 < M,N < 1000

2.       บรรทัดที่สองระบุขนาดพื้นที่บริการของร้าน (K) โดยที่ 0 < K < M และ 0 < K < N

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

ข้อมูลส่งออก

จำนวนประชากรภายในพื้นที่บริการที่ดีที่สุด

ที่มา : การแข่งขันคอมพิวเตอร์โอลิมปิกระดับชาติครั้งที่ 8 (SUTOI8)