2037 : Hermes
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]  

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