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

พื้นที่ของประเทศแอฟริกาใต้มีลักษณะเป็นตารางสี่เหลี่ยมจัตุรัสขนาด N×N ช่อง แต่ละช่องจะมีทองแดง เงิน และทองคำอยู่ในปริมาณต่างๆ คุณต้องการสร้างเหมืองทองแดง เหมืองเงิน และเหมืองทองคำ ซึ่งแต่ละเหมืองจะเป็นสี่เหลี่ยมจัตุรัสขนาด K×K ช่อง ปริมาณแร่แต่ละชนิดที่คุณขุดได้จะมีค่าเท่ากับผลรวมของปริมาณแร่ชนิดนั้นในพื้นที่เหมืองของคุณ เหมืองแร่แต่ละเหมืองสามารถซ้อนทับกันได้โดยไม่มีผลกระทบต่อการขุดแร่

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

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

ข้อมูลนำเข้า
บรรทัดแรกระบุจำนวนเต็ม N และ K (1 ≤ K ≤ N ≤ 1,000) แทนขนาดของพื้นที่ทั้งหมด และขนาดของเหมืองแร่แต่ละเหมือง

อีก N บรรทัดต่อมา ระบุจำนวนเต็มบวกบรรทัดละ N ตัว แทนปริมาณทองแดงในพื้นที่แต่ละช่อง

อีก N บรรทัดต่อมา ระบุจำนวนเต็มบวกบรรทัดละ N ตัว แทนปริมาณเงินในพื้นที่แต่ละช่อง

อีก N บรรทัดต่อมา ระบุจำนวนเต็มบวกบรรทัดละ N ตัว แทนปริมาณทองคำในพื้นที่แต่ละช่อง

ปริมาณของแร่แต่ละชนิดในพื้นที่แต่ละช่องจะมีค่าไม่เกิน 500

ข้อมูลส่งออก
มีบรรทัดเดียว แสดงปริมาณรวมของแร่ทั้งสามชนิดที่มากที่สุดที่คุณสามารถขุดได้

การให้คะแนน
30% ของข้อมูลทดสอบ จะมี N ≤ 15
50% ของข้อมูลทดสอบ จะมี N ≤ 50

ที่มา
การแข่งขัน IOI Thailand League เดือนมิถุนายน 2553
โจทย์โดย: สุธี เรืองวิเศษ

ตัวอย่างข้อมูลนำเข้า ตัวอย่างข้อมูลส่งออก
3 2
1 2 3
4 5 6
7 8 9
1 2 3
4 5 6
7 8 9
9 8 7
6 5 4
3 2 1
84
4 2
7 7 1 1
7 7 1 1
1 1 1 1
1 1 1 1
1 8 8 1
1 8 8 1
1 1 1 1
1 1 1 1
1 1 1 1
9 9 1 1
9 9 1 1
1 1 1 1
96

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

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