Masala #0424

Xotira 16 MB Vaqt 1000 ms
14

Snake game

Eski telefonlarda "Iloncha" oyinini o'ynaganmisiz? Agar o'ynamagan bo'lsangiz hozir sizga o'yin qoidalarini tanishtiraman.
1. Dastlab iloncha 1 birlik uzunlikka ega bo'ladi.
2. Har bir yeyilgan olmachalar uchun uning uzunligi 1 birlikka oshib boradi.
3. Yangi qo'shiladigan ilonchaning bo'lagi, uning oxirgi bo'lagining harakat yo'nalishiga mos ravishta va shu bo'lak ketidan joy oladi.
4. Iloncha yo'lida to'siq bo'lmagan hollarda o'ngga, chapga, yuqoriga va pastga harakat qila oladi.
Iloncha o'yini \(8 \times 8\) maydonida bo'ladi va iloncha \(1 \times 1\) katakchadan o’yinni boshlaydi. Sizga mos ravishta ketma-ket paydo bo'luvchi N ta olmachalarning kordinatalari beriladi. Ilonchaning vasifangiz barcha olmachalarni yeb bitirish, ammo buning uchun ilonchaning boshi eng kam masofani bosib o’tishi kerak bo'ladi. (Ilonchaning tanasi va maydonning chetki qismlari to'siqlar hisoblanadi)


Kiruvchi ma'lumotlar:

Birinchi qatorda olmachalar soni \(N\). Keyingi \(N\) ta qatorda esa ketma-ket paydo bo'luvchi olmachalarning kordinatalari \(x_i​,y_i\)​. \((1 \le N \le 10, 1 \le x_i​,y_i​ \le 8)\)


Chiquvchi ma'lumotlar:

Barcha olmachalarni yeyish uchun ilonchaning boshi sarflaydigan eng qisqa yo'lning uzunligini toping. (masala yechimga ega ekanligi kafolatlanadi.)


Misollar
# input.txt output.txt
1
3
1 8
8 8
8 1
21
2
2
8 1
2 1
15
3
2
2 1
8 1
7