dungeon ลับแห่งหนึ่งมีลักษณะเป็นรูปกล่องสี่เหลี่ยมมุมฉากซึ่งถูกแบ่งออกเป็นห้องย่อยๆขนาด W x H x L โดยมีทางเข้าที่ (1, 1, 1) และมีทางออกที่ (W, H, L)
การเดินทางใน dungeon นั้นจะสามารถเดินไปยังห้องที่ติดกันอยู่ได้ คือ ด้านบน, ด้านล่าง, ด้านขวา, ด้านซ้าย, ด้านหน้า, ด้านหลัง (สำหรับห้องที่อยู่ขอบเช่น (1, 1, 1) จะเดินไปได้เพียงข้างขวา ข้างล่าง ข้างหลัง) เมื่อออกห้องใด ๆ แล้ว ห้องนั้นจะถูกปิดจากทุกทิศทุกทางทำให้เข้าไม่ได้อีกเลยไม่ว่าจะจากทิศใดก็ตาม ในแต่ละห้องจะมีแต้มต่าง ๆ อยู่ คุณอยากจะเก็บแต้มให้มากที่สุดเท่าที่จะเป็นไปได้ อย่างไรก็ตาม หากว่าเก็บแต้มได้มากที่สุดแต่ออกจาก dungeon ไม่ได้ก็จะไม่มีประโยชน์แต่อย่างใด
งานของคุณคือเขียนโปรแกรมหาแต้มรวมให้มากที่สุดเท่าที่จะเป็นไปได้ที่ทำให้เมื่อเดินทางแล้วสามารถออกจาก dungeon ได้ด้วย
ข้อมูลนำเข้า
บรรทัดแรกมีจำนวนเต็มบวก W H L (1 <= W, H, L <= 100)
ต่อมาจะมีข้อมูลอีก L กลุ่ม แต่ละกลุ่มมีตาราง H แถว แต่ละแถวมีข้อมูล W ตัว
ข้อมูลแต่ละตัวคือแต้ม 1 <= V
ijk <= 1 000 000
ข้อมูลส่งออก
บรรทัดเดียว มีจำนวนเต็มบอกถึงแต้มรวมมากสุดที่สามารถเก็บได้และสามารถออก dungeon ได้ด้วย
ที่มา
การแข่งขัน TUMSO ครั้งที่ 9
โจทย์โดย สรวีย์ พรเจริญวาสน์
ตัวอย่างข้อมูลนำเข้า | ตัวอย่างข้อมูลส่งออก |
2 2 3
5 10
11 12
11 4
25 10
9 50
31 100 | 268 |
ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้