1068 : ล้อมกรอบ (border)
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 16 megabyte(s)
    กำหนดตารางขนาด N คูณ N (1 ≤ N ≤ 100) โดยที่ขอบของตารางแต่ละขอบมีเลขเขียนกำกับเอาไว้ เช่น


    เราต้องการล้อมกรอบพื้นที่จำนวน K (1 ≤ K ≤ N2) ช่อง เช่น ถ้า K = 5 วิธีหนึ่ง ที่อาจจะล้อมกรอบพื้นที่เป็นดังต่อไปนี้
 

 

    การล้อมกรอบต้องเสียค่าใช้จ่าย ซึ่ง เราสามารถคำนวณค่าใช้จ่ายได้ตามขั้นตอนต่อไปนี้
 
 
    1. จำแนกขอบที่ล้อมกรอบบริเวณ K ช่องดังกล่าว (ขอบเส้นหนาในรูปข้างบน) ออกเป็นสี่ชนิด ได้แก่
  • ขอบบน คือ ขอบแนวนอนที่อยู่บนสุดของตาราง หรือช่องที่อยู่ใต้มันเป็นช่องที่ถูกล้อมกรอบ และช่องที่อยู่เหนือมันเป็นช่องที่ไม่ถูกล้อมกรอบ ในตัวอย่างคือขอบที่มีหมายเลข 70, 9, 30, และ 1
  • ขอบล่าง คือ ขอบแนวนอนที่อยู่ล่างสุดของตาราง หรือช่องที่อยู่เหนือมันเป็นช่องที่ถูกล้อมกรอบ และช่องที่อยู่ใต้มันเป็นช่องที่ไม่ถูกล้อมกรอบ ในตัวอย่างคือขอบที่มีหมายเลข 57, 10, 55, และ 45
  • ขอบซ้าย คือ ขอบแนวตั้ง ที่อยู่ซ้ายสุดของตาราง หรือช่องที่อยู่ด้านขวาของมันเป็นช่องที่ถูกล้อมกรอบ และช่องที่อยู่ด้านซ้ายของมันเป็นช่องที่ไม่ถูกล้อมกรอบ ในตัวอย่างคือขอบที่มีหมายเลข 23, 39, และ 99
  • ขอบขวา คือ ขอบแนวตั้ง ที่อยู่ขวาสุดของตาราง หรือช่องที่ทางด้านซ้ายของมันเป็นช่องที่ถูกล้อมกรอบ และช่องที่อยู่ด้านขวาของมันเป็นช่องที่ไม่ถูกล้อมกรอบ ในตัวอย่างคือ ขอบที่มีหมายเลข 37, 98, และ 48
    2. ทำการคำนวณค่าใช้จ่ายโดยใช้สูตรต่อไปนี้
 
ค่าใช้จ่าย = 3xผลรวมเลขขอบบน + 5xผลรวมเลขขอบซ้าย - 3xผลรวมเลขขอบล่าง - 5xผลรวมเลขขอบขวา
 
    ดังนั้น ค่าใช้จ่ายในการล้อมกรอบดังรูปข้างบนจึงมีค่าเท่ากับ
 
3x(70+9+23+30+1) + 5x(23+39+99) - 3x(57+10+55+45) - 5x(37+98+48) = -212

     เราอาจจะล้อมพื้นที่ 5 ช่องได้อีกหนึ่ง วิธี คือ



    โดยในกรณีนี้ค่าใช้จ่ายในการล้อมกรอบจะมีค่าเท่ากับ
3x(57+10+81) + 5x(42+14+85) - 3x(27+97+83) - 5x(98+29+53) = -372

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

ข้อมูลนำเข้า
    บรรทัดแรก มีจำนวนเต็มบวก N และ K ซึ่งมีขอบเขตดังที่ได้กล่าวไปแล้วข้างต้น
ต่อมาอีก 2N+1 บรรทัด เป็นข้อมูลหมายเลขที่อยู่บนขอบ เรียงจากเหนือลงใต้และซ้ายไปขวา กล่าวคือ
    ในบรรทัดที่ 1+i เมื่อ i เป็นเลขคู่จะมีตัวเลขอยู่ N ตัว แสดงหมายเลขของขอบแนวนอนเรียงจากซ้ายไปขวา
    ในบรรทัดที่ 1+i เมื่อ i เป็นเลขคี่จะมีตัวเลขอยู่ N+1 ตัว แสดงหมายเลขของขอบแนวตั้งเรียงจากซ้ายไปขวา
    หมายเลขบนขอบแต่ละหมายเลขเป็นจำนวนเต็มที่ไม่เป็นลบที่มีค่าไม่เกิน 10,000

ข้อมูลส่งออก
    บรรทัดแรก พิมพ์ค่าใช้จ่ายที่น้อยที่สุดที่เป็นไปได้ในการล้อมกรอบพื้นที่ K ช่อง

ทีมา: การแข่งขัน YTOPC กุมภาพันธ์ 2552

ตัวอย่างข้อมูลนำเข้า ตัวอย่างข้อมูลส่งออก
4 5
11 42 30 56
49 85 23 37 15
70 9 81 60
39 2 42 98 6
57 10 55 77
14 32 28 29 30
27 64 83 1
71 85 53 99 48
5 97 68 45
-1170

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

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