อุลตร้าแมนเป็นสัตว์สังคม (สิ่งมีชีวิตที่อยู่กันเป็นกลุ่ม) แน่ นอน ในกลุ่มของอุลตร้าแมนย่อมต้องมี “อุลตร้าแมนจอมโจรยอดนักฆ่า” ซึ่งสร้างความเดือดร้อนให้กับสังคมอุลตร้าแมนอย่างมาก ดังนั้นในกลุ่มของอุลตร้าแมนจึงได้มีการแต่งตั้ง “อุลตร้าแมนลาดตระเวน” เพื่อรักษาความปลอดภัยในชุมชนอุลตร้าแมน

            ลักษณะของหมู่บ้านอุลตร้าแมนจะประกอบด้วยบ้านครอบครัวอุลตร้าแมนทั้งสิ้น n หลัง และจะมี “อุลตร้าแมนลาดตระเวน” ทั้งสิ้น k คน ทำให้เราสามารถแบ่งบ้านครอบครัวอุลตร้าแมนทั้ง n หลัง ออกเป็น k กลุ่ม เพื่อให้อยู่ในความรับผิดชอบของ “อุลตร้าแมนลาดตระเวน” แต่ละบุคคล

            บ้านครอบครัวอุลตร้าแมนแต่ละหลังจะอยู่ในตำแหน่งพิกัด (x,y) เมื่อ x และ y เป็นจำนวนนับ บนกริดขนาด 1000*1000 ซึ่งจะทำให้บ้านแต่ละหลังจะมีทางเดินหากัน (เอดจ์) เชื่อมถึงกันโดยบ้านที่อยู่พิกัด (x₁,y₁) และ (x₂,y₂) จะมีระยะห่างกัน sqrt( (x1-x2)^2 + (y1-y2)^2 ) 

            สมมติ ให้ “อุลตร้าแมนลาดตระเวน” คนหนึ่งดูแลบ้านครอบครัวอุลตร้าแมน จำนวนหนึ่ง เราจะนิยาม “ค่าความเหนื่อยของอุลตร้าแมนลาดตระเวน” คนนี้ ให้มีค่าเท่ากับ ระยะห่างที่มากที่สุดเมื่อเราสร้างทางเชื่อมระหว่างบ้านครอบครัวอุลตร้าแม นทั้งสิ้น p-1 เส้นทาง (เมื่อมีบ้านครอบครัวอุลตร้าแมนทั้งสิ้น p หลัง) เพื่อเชื่อมบ้านครอบครัวอุลตร้าแมนทั้ง p หลังเข้าด้วยกัน (พูดง่ายๆคือระยะทางของเอดจ์ที่มากที่สุดเมื่อคุณสร้าง minimum spanning tree บนโหนดทั้ง p โหนดจากเอดจ์ทั้งสิ้น p*(p-1)/2 เอดจ์)

            เรากำหนดให้ค่าความเหนื่อยทั้งมวล ของเหล่า “อุลตร้าแมนลาดตระเวน” คือค่าความเหนื่อยที่มากที่สุดของ “อุลตร้าแมนลาดตระเวน” คนใดคนหนึ่ง

            กำหนดพิกัดของบ้านครอบครัวอุลตร้าแมนทั้ง n หลัง และจำนวนของ “อุลตร้าแมนลาดตระเวน” k จงหาค่าความเหนี่อยทั้งมวลที่น้อยที่สุด

ข้อมูลนำเข้า

บรรทัดแรกประกอบด้วยจำนวนนับ n และ k แทนจำนวนของบ้านครอบครัวอุลตร้าแมน และจำนวนของ “อุลตร้าแมนลาดตระเวน” ( 1 < k < n < 1000 )

ถัดมา n บรรทัดประกอบด้วยจำนวนนับ 2 จำนวน x และ y แทนพิกัดของบ้านครอบครัวอุลตร้าแมนแต่ละหลัง ( 1 < x, y < 1000 )

ข้อมูลส่งออก

บรรทัดแรกและบรรทัดเดียวแสดงค่า กำลังสอง ของค่าความเหนื่อยทั้งมวลของเหล่าอุลตร้าแมน เมื่อคุณจัดสรรความรับผิดชอบของเหล่าอุลตร้าแมนอย่างดีที่สุด

หมายเหตุ

          30% ของชุดทดสอบทั้งหมด n < 10
            50% ของชุดทดสอบทั้งหมด n < 100
            100% ของชุดทดสอบทั้งหมด n < 1000

โจทย์โดย : สรวิทย์  สุริยกาญจน์ ( PS.int ) และแนวคิดจากค่าย สสวท. ค่ายที่ 2 ระยะ 2 ประจำปี 2553