Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 64 megabyte(s)
บ้านของคุณมีลักษณะเป็นกริดสี่เหลี่ยมขนาด N*N ในแต่ละช่องของกริดนั้น คุณได้เก็บของสำคัญของคุณแต่ละชิ้นไว้ในแต่ละช่อง โดยที่ช่อง (i,j) จะมีของมูลค่า Vi,j ของคุณเก็บอยู่
วันหนึ่ง ได้เกิดเหตุการณ์ไฟไหม้วินาศกรรมครั้งยิ่งใหญ่ขึ้นที่บ้านของคุณ ไฟนั้นจะเริ่มที่พิกัด (1,1) ซึ่งก็คือช่องซ้ายบนของบ้าน และไฟจะลามไปเรื่อยๆอย่างไม่มีที่สิ้นสุด !
ลักษณะการลุกลามของไฟจะความเฉพาะตัวคือ “ทุกๆ 1 นาที ช่องที่ติดกับช่องที่มีไฟอยู่ ไม่ว่าจะติดทางซ้าย ขวา บน ล่าง จะติดไฟด้วย (ไม่นับแนวทแยง)”
คุณต้องการจะปกป้องทรัพย์สมบัติของคุณไว้ให้ได้มากที่สุด ซึ่งทุกๆ 1 นาที คุณจะสามารถอพยพของของคุณออกไปจากบ้านได้ 1 ชิ้น (สังเกตได้ว่าสมบติที่ช่อง (1,1) ไม่สามารถอพยพออกไปได้ทันอย่างแน่นอน)
จงเขียนโปรแกรมหาว่าจะสามารถอพยพของออกไปจากบ้านได้มูลค่ารวมมากที่สุดเท่าไร
ข้อมูลนำเข้า
บรรรทัดแรก : จำนวนนับ N แทนขนาดบ้านของคุณ ( 1 < N < 1000 )
บรรทัดถัดไป N บรรทัด แต่ละบรรทัดประกอบด้วยจำนวนนับ N จำนวน โดยตัวเลขบรรทัดที่ i ลำดับที่ j จะแทนค่า Vi,j ( 1 < Vi,j < 10 000 )
ข้อมูลส่งออก
บรรทัดแรกและบรรทัดเดียว แสดงมูลค่ารวมของสมบัติที่คุณอพยพออกจากบ้านได้ทัน
| ตัวอย่างข้อมูลนำเข้า | ตัวอย่างข้อมูลส่งออก |
| 5 50 36 10 13 2 17 5 16 42 41 49 12 38 9 25 18 4 36 31 11 30 6 3 46 50 | 333 |
| 5 30 46 17 43 35 31 24 7 8 49 42 11 11 3 31 32 10 42 35 35 27 3 29 47 43 | 347 |
ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้