C. Жаргалтай ферм 5

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Жаргалтай ферм 5 тоглоомын зохиогчид үнээнүүдийн бэлчиж байгаа үзэгдлийг тоглоомдоо нэмэхээр шийджээ. Уг тоглоом дахь үнээнүүд нь үнэхээр удаан бөгөөд тэд маш удаан хөдөлдөг. Бараг тэдгээрийн хөдөлж байгаа нь тэд зүгээр л зогсож байгаа мэт харагддаг байна. Гэсэн хэдий ч махчин амьтад үргэлж тэдний араас мөшгөсөөр байх юм.

Үүний тулд залуу тоглогч Вася уг тоглоомын хоньчинг нэгэн ижил битүү замын дагуу үнээнүүдийг бэлчээрлүүлж байхаар байрлуулжээ. Үнээнүүд нь замаар хязгаарлагдсан бэлчээрийн талбай дотроо заавал байх нь үнэхээр чухал бөгөөд эс бөгөөс талбайгаас гарсан үнээнүүд эрт орой хэзээ нэгэн цагт махчин амьтдад идүүлэх юм. Үнээнүүдийг аюулгүй байгаа эсэхэд баттай итгэлтэй байхын тулд Вася уг талбайг хязгаарласан зам нь аль болох хамгийн бага хугацаанд баригдахыг хүсэж байгаа юм.

Уг шинэ тоглоом нь олон төрлийн ялгаатай төхөөрөмжүүд дээр ажиллах бөгөөд утсан дээр ч мөн ажиллана. Иймээс тоглоомыг хөгжүүлэгчид бутархай тоо бүхий арифметик ашиглахаа больсон ба зөвхөн бүхэл тоон арифметик хэрэглэхээр болжээ. Тоглоомын үнээнүүд болон хоньчин хавтгай дээрх бүхэл тоон координатуудтай цэгүүдээр дүрслэгдэх ба тоглоомыг тоглох хугацаа нь ээлжээр өгөгдөх юм. Тоглоомын ээлж болгонд хоньчин өөрийн байгаа газраа үлдэх эсвэл дараах 8-н чиглэлийн аль нэг уруу 1 алхам урагшлах юм: хөндлөн, босоо, эсвэл диагоналийн дагуу, ө.х дээш, доош, баруун, зүүн, баруун дээш, зүүн дээш, баруун доош, зүүн доош гэсэн 8-н чиглэл байна. Координатууд нь үргэлж бүхэл тоонууд байх учраас хөндлөн болон босоо алхмын урт нь $1$-тэй тэнцүү байна. Харин диагоналийн дагуу хийсэн алхмын урт нь -той тэнцүү байна. Үнээнүүд нь огт хөдлөхгүй бөгөөд та хоньчинг нийт сүргийг тойрон явж замыг барихад шаардагдах хамгийн цөөхөн алхмын тоог олох юм. Хоньчин зам барихад хугацаа зарцуулахгүй бөгөөд зөвхөн нийт сүргийг тойрон явахад шаардагдах алхмын тоог хамгийн цөөн байлгахад болох юм.

Оролт

Эхний мөрөнд бүхэл тоо $N$ өгөгдөх ба энэ нь нийт сүрэгт байх үнээнүүдийн тоог илэрхийлнэ ($1 ≤ N ≤ 10^{5}$). Дараагийн $N$ мөрийн мөр болгонд 2 бүхэл тоо $X_{i}$ болон $Y_{i}$ өгөгдөх ба эдгээр нь нэг үнээний координатуудыг илэрхийлнэ ($|X_{i}|, |Y_{i}| ≤ 10^{6}$). Хэд хэдэн үнээнүүд нь нэг ижил цэг дээр зогссон байж болно.

Гаралт

Замыг барихын тулд шаардлагатай хамгийн бага алхмын тоог хэвлэнэ үү.

Орчуулсан: Баатархүү

Жишээ тэстүүд

Оролт
4
1 1
5 1
5 3
1 3
Гаралт
16

Тэмдэглэл

Жишээ тестийн зурагт координатын тэнхлэгийн нүднүүдийг саарал өнгөөр, координатын тэнхлэгүүдийг хар өнгөөр, үнээнүүдийг улаан өнгөөр, хайж буй замаа ногоон өнгөөр будсан байна.

Сэтгэгдлүүдийг ачааллаж байна...