Problem type : Batch
Time limit : 3.0 second(s)
Memory limit : 16 megabyte(s)
ในเมืองที่ทันสมัยของเทพเจ้ากรีก ถนนจะถูกกำหนดด้วยกริดซึ่งประกอบด้วยพิกัดจำนวนเต็มโดยที่ถนนจะขนานกับแกน x และ y พูดง่ายๆคือ สำหรับแต่ละจำนวนเต็ม Z จะมีถนนแนวนอนที่ y=Z และถนนแนวตั้งที่ x=Z จากรูปแบบนี้ทำให้คู่พิกัดจะแสดงถึงทางแยกของถนน
ในวันที่อากาศร้อนอบอ้าว เทพเจ้าแต่ละองค์จะนั่งอยู่ตามร้านกาแฟที่ทางแยกถนนต่างๆ เทพเจ้า"แอร์-เมส" (เทพแห่งการ ส่งจดหมาย) ต้องการที่จะส่งจดหมายลับให้กับเทพเจ้าแต่ละองค์ที่อยู่ตามร้านกาแฟต่างๆ โดยการเดินไปตามถนน แต่ละจดหมายจะถูกกำหนดไว้สำหรับเทพเจ้าองค์หนึ่งๆ มันไม่สำคัญที่เทพเจ้าองค์อื่นจะเห็นจดหมายหรือไม่
จดหมายจะถูกให้เทพเจ้าตามลำดับที่ถูกกำหนดเท่านั้น และ "แอร์-เมส" ได้จัดเรียงลำดับตามพิกัดของร้านกาแฟเรียบร้อยแล้ว "แอร์-เมส"จะเริ่มต้นที่ (0,0) และจะส่งจดหมายไปยังเทพเจ้าองค์ต่างๆ โดยหาก"แอร์-เมส"ต้องการที่จะส่งจดหมายให้กับเทพเจ้าที่นั่งอยู่ที่ร้านกาแฟพิกัด (Xi,Yi) "แอร์-เมส"ก็เพียงแค่อยู่ที่จุดที่อยู่บนถนนแนวตั้งเดียวกันหรือแนวนอนเดียวกันเท่านั้น (พูดง่ายๆคืออยู่ที่ (Xi,Z) หรือ (Z,Yi) ใดก็ได้ เมื่อ Z คือจำนวนเต็มใดๆ) เมื่อ "แอร์-เมส" ส่งจดหมายให้กับเทพเจ้าครบตามลำดับแล้ว "แอร์-เมส" ก็จะหายไป
คุณจะ ต้องเขียนโปรแกรมที่เมื่อได้รับลำดับของพิกัดร้านกาแฟแล้ว จงหาระยะทางรวมที่น้อยที่สุดที่"แอร์-เมส"จำเป็นจะต้องเดินเพื่อส่งจดหมายทั้ง หมด
INPUT
บรรทัดแรกประกอบด้วยจำนวนเต็ม N แทนจำนวนจดหมายที่จะต้องส่ง
ถัดมา N บรรทัดแต่ละบรรทัดจะประกอบด้วยจำนวนเต็ม 2 จำนวนแทนพิกัดของเทพเจ้าที่จะได้รับจดหมาย
OUTPUT
บรรทัดแรกและบรรทัดเดียวระบุระยะทางที่น้อยที่สุดที่"แอร์-เมส"จะต้องเดินทางในการส่งจดหมายทั้งหมด
NOTE : ในข้อมูลทดสอบทั้งหมด 1 < N < 20 000 , -1000 < Xi,Yi < 1000
ยิ่งไปกว่านั้น ใน 50% ของข้อมูลทดสอบ 1 < N < 80
ที่มา: International Olympiad In Informatics 2004
| ตัวอย่างข้อมูลนำเข้า | ตัวอย่างข้อมูลส่งออก |
| 5 8 3 7 -7 8 1 -2 1 6 -5 | 11 |
ความช่วยเหลือ: Hint[1] Hint[2]