1044 : Road Cut
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 64 megabyte(s)
คณะกรรมการผู้บริหารเมืองแห่งหนึ่งต้องการทำการตัดถนนผ่านพื้นที่ใจกลางเมือง โดยความต้องการของเมืองคือการตัดถนนเป็นเส้นตรงผ่านเมืองเป็นเส้นตรงทางทิศทางใดก็ได้ ระหว่างการตัดถนนผ่านทางด้านทิศตะวันตกไปยังด้านทิศตะวันออก (ซ้ายไปขวา) หรือทางด้านทิศเหนือไปยังด้านทิศใต้ (บนลงล่าง) ซึ่งพื้นที่ดังกล่าวมีมูลค่าของพื้นที่ในแต่ละส่วนไม่เท่ากัน  นอกเหนือจากนั้นเมื่อตัดถนนแล้วจะทำให้พื้นที่ที่อยู่ติดถนนมีมูลค่าสูงขึ้น เพื่อให้การตัดถนนทำให้เกิดความเสียหายน้อยที่สุดและเพื่อประโยชน์ของเมืองโดยรวม การตัดถนนจึงควรตัดผ่านพื้นที่ที่มีมูลค่าต่ำที่สุดและยังทำให้มูลค่าพื้นที่โดยรวมของเมืองมีมูลค่าเพิ่มขึ้นสูงสุดอีกด้วย

โจทย์

จงเขียนโปรแกรมเพื่ออ่านข้อมูลนำเข้าของมูลค่าพื้นที่ย่อยภายในเมือง และการเปลี่ยนแปลงมูลค่าของพื้นที่ย่อยเมื่อมีการตัดถนนผ่าน ทั้งนี้กำหนดให้พื้นที่ภายในเมืองมีรูปทรงเป็นสี่เหลี่ยมผืนผ้าหรือสี่เหลี่ยมจัตุรัสเสมอ จากนั้นให้คำนวณหาเส้นทางที่ทำให้มูลค่าพื้นที่ของเมืองโดยรวมมีมูลค่าสูงที่สุดเพื่อให้คณะกรรมการนำไปพิจารณาทำการตัดถนน โดยกำหนดให้เส้นทางที่ถูกทำเป็นถนนจะมีมูลค่าพื้นที่เหลือ 0



ข้อมูลนำเข้า
บรรทัดแรกของข้อมูลนำเข้าเป็นจำนวนเต็มสองตัว n (2 < n <= 100) และ m (2 < m <= 100) ซึ่งเป็นขนาดของพื้นที่เมือง
ใน n บรรทัดถัดไป (เริ่มจากบรรทัดที่ 2 ถึงบรรทัดที่ n+1) เป็นข้อมูลของมูลค่าพื้นที่ย่อยจากเหนือลงใต้ โดยบรรทัดที่ i+1 จะแสดงข้อมูลของพื้นที่ย่อยในแถวที่ i (1 <= i <= n) โดยที่แต่ละบรรทัดจะมีตัวเลขทั้งหมด m ตัว (ตัวเลขแต่ละตัวจะถูกคั่นด้วยช่องว่าง) โดยตัวเลขแต่ละตัวในแต่ละบรรทัดเป็นจำนวนเต็มมีค่าระหว่าง 0 ถึง 100
ใน n บรรทัดถัดไป (เริ่มจากบรรทัดที่ n+2) เป็นข้อมูลการเปลี่ยนแปลงมูลค่าของพื้นที่ย่อยเมื่อมีถนนตัดผ่าน โดยบรรทัดที่ n+i+1 จะแสดงข้อมูลของการเปลี่ยนแปลงมูลค่าพื้นที่ย่อยในแถวที่ i (1 <= i <= n) โดยที่แต่ละบรรทัดจะมีตัวเลขทั้งหมด m ตัว (ตัวเลขแต่ละตัวจะถูกคั่นด้วยช่องว่าง) โดยตัวเลขแต่ละตัวในแต่ละบรรทัดเป็นจำนวนเต็มมีค่าระหว่าง 0 ถึง 20 (ซึ่งอาจจะทำให้มูลค่าของพื้นที่ย่อยมีค่าเกิน 100 ได้)

ข้อมูลส่งออก
มีทั้งหมด 1 บรรทัด มีตัวเลข 1 ตัวซึ่งแสดงถึงมูลค่ารวมของพื้นที่ภายในเมืองหลังจากทำการตัดถนนเรียบร้อยแล้ว

ที่มา: การแข่งขันคณิตศาสตร์ วิทยาศาสตร์ โอลิมปิกแห่งประเทศไทย สาขาวิชาคอมพิวเตอร์ ประจำปี 2550

ตัวอย่างข้อมูลนำเข้า ตัวอย่างข้อมูลส่งออก
5 4
2 3 2 1
4 5 8 4
2 5 3 2
1 4 0 2
2 1 8 1
1 2 3 2
2 2 2 1
2 1 1 2
1 2 1 0
1 1 1 0
62

ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้

กำลังออนไลน์: 13 ผู้เยี่ยมชมและ 3 สมาชิก (1 บอท)