1139 : อาคารเรียน (campus)
Problem type : Batch
Time limit : 0.5 second(s)
Memory limit : 32 megabyte(s)
ณ สถาบันเทคโนโลยีแห่งหนึ่งทางภาคตะวันออกเฉียงเหนือ มีหอพักอยู่ทั้งหมด N หอ ตั้งอยู่บนพิกัดที่เป็นจำนวนเต็มบนระนาบสองมิติ แต่ละหอก็มีนักเรียนจำนวนหนึ่งพักอยู่

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

เนื่องจากทางเดินในสถาบันแห่งนี้มีลักษณะเป็นตารางสี่เหลี่ยมจัตุรัส หากหอพักของนักเรียนตั้งอยู่ที่พิกัด (x1, y1) และอาคารเรียนตั้งอยู่ที่พิกัด (x2, y2) นักเรียนจะต้องเดินมาเรียนเป็นระยะทาง 
|x- x2| + |y1 - y2| นอกจากนี้ หอพักแต่ละหอยังมีขนาดเล็กมาก จึงอาจมีหอพักมากกว่า 1 หอ ตั้งอยู่ที่พิกัดเดียวกันได้ และตำแหน่งที่จะสร้างอาคารเรียน อาจตรงกับพิกัดของหอพักบางหอก็ได้

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

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

อีก N บรรทัดต่อมา ในบรรทัดที่ i+1 (1 ≤ i ≤ N) ระบุจำนวนเต็ม Xi, Yi และ Si (1 ≤ Xi,Yi ≤ 1,000,000,000; 1 ≤ Si ≤ 1,000) แทนพิกัดบนแกน X พิกัดบนแกน Y และจำนวนนักเรียนในหอพักที่ i

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

การให้คะแนน
30% ของข้อมูลทดสอบ จะมี Si = 1 สำหรับทุกจำนวนเต็ม i  (1 ≤ i ≤ N )
60% ของข้อมูลทดสอบ จะมี N ≤ 100,000
20% ของข้อมูลทดสอบ จะสอดคล้องกับเงื่อนไขด้านบนทั้งสองข้อ

ที่มา
โจทย์โดย: สุธี เรืองวิเศษ

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

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

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