มีกล่องลูกบาศก์บรรจุพลังงานว่างเปล่า N กล่อง อยู่ในสเปซ K มิติ เดิมทีกล่องแต่ละกล่อง ไร้ซึ่งพลังงาน เราได้มีเชื้อพลังงานเป็นจุด M จุดเติมเข้าไปในสเปซ โดยเมื่อจุดพลังงานเข้าไปอยู่ภายในหรืออยู่บนผิวกล่องใด จะทำให้พลังงานในกล่องนั้น 1 หน่วย และจุดพลังงาน 1 จุดอาจเพิ่มพลังงานให้กล่องมากกว่า 1 กล่อง

          พิกัดของกล่องจะบอกจุดมุม 2 จุดที่อยู่ห่างกันมากที่สุดในแต่ละกล่อง ส่วนพิกัดจุดพลังงานนั้น จะบอกในรูปของจุด 1 จุดเท่านั้น โดยที่พิกัดจะบอกในรูปของ (x₁,x₂,x₃,..,x_k) โดยมีพิกัดบนระบบจำนวนเต็มที่อยู่ระหว่าง –10⁹ กับ 10⁹

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

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

บรรทัดที่ 1 : จำนวนเต็มบวก N, M, K คั่นด้วยช่องว่าง ( 1 < N, M < 1000 )
บรรทัดที่ 2 ถึง N+1 : จำนวนเต็ม x₁,x₂,x₃,…,x_k,y₁,y₂,y₃,…,y_k คั่นด้วยช่องว่าง บอกพิกัดจุดมุม x และ y ของแต่ละกล่อง
บรรทัดที่ N+2 ถึง N+M+1 : จำนวนเต็ม x₁,x₂,x₃,…,x_k คั่นด้วยช่องว่าง บอกพิกัดของจุดแต่ละจุด

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

บรรทัดที่ 1 : จำนวนเต็ม C บอกจำนวนของกล่องที่แข็งแกร่ง
บรรทัดที่ 2 : จำนวนเต็ม a₁,a₂,…,a_C คั่นด้วยช่องว่าง โดยจะหมายถึงกล่องที่แข็งแกร่งแต่ละกล่อง ซึ่ง a₁ < a₂ < a₃ < … < a_C

โจทย์โดย : พี่โมโม่ (Nautilus Processor)

ที่มา : ศูนย์ สอวน. โรงเรียนมหิดลวิทยานุสรณ์