Програмчлалын олимпиадын бодлогын архив

Казань 

Казань 2016-д оролцох сурагчдын нэрс нэгэнт тодорчээ. Харин одоо тэд хамтдаа Улаанбаатараас Казань орох замын маршрутыг гаргах гэж байна. Гэвч тэд Казань орохын тулд заавал N тооны хотыг дайран өнгөрөх ёстой гэдгийг ойлгов.

Бодлогын нөхцөл:

• Хот бүрийг нэг л удаа дайрна.
• Хамгийн эцсийн зогсоол Казан юм.
• Та бүгд яг одоо Улаанбаатарт байгаа.
• Хотуудын хоорондох зай D= |x[i] - x[j]| + |y[i] - y[j]| гэж тодорхойлогдоно

Тестийн 30 %-д (N<= 8)

Тестийн 100 %-д (N<= 18)

Input

Оролтын эхний мөрөнд  (0<= N<= 18) тоо буюу заавал дайрах ёстой хотуудын тоо. Үүний дараа (N + 2) мөрөнд хотуудын байрлал буюу (|x|<= 1000000, |y|<= 1000000) координатууд өгөгдөнө. Хамгийн эхний болон Хамгийн сүүлийн цэгүүдийг харгалзан Улаанбаатар болон, Казань хотууд гэж үзнэ.

Output

Улаанбаатараас Казань орох хамгийн богино замын нийт уртыг гарга.

Example

Input:
2
0 0
2 1
2 -2
10 -2

Output:
14
 
Тайлбар : /Улаанбаатар/ буюу (0, 0) цэгээс эхлэн -> (2, 1) -> (2 - 2) ->/Казан/буюу(10, - 2) орно.
Иймд зардал 3 + 3 + 8 = 14 гарна.
Энэ жишээний дараагийн явах боломжит маршрут(0, 0) -> (2, -2) -> (2, - 2) -> (10, -2).
Гэвэл зардал 4 + 3 + 11 = 18 гарна.