eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Игра

Игра

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Вова играет в очень увлекательную игру на компьютере, которая называется "Робот и сокровища". В этой игре на бесконечном клетчатом поле в некоторых клетках располагаются сундуки с драгоценностями. Игроку предлагается управлять роботом, который вначале необходимо поставить в одну из клеток, а далее собрать все сокровища. Робот забирает ценные материальные объекты, когда находится с ними в одной клетке. Робот может перемещаться в любую из 8 соседних клеток. Он делает это по нажатию специальной клавиши на клавиатуре.

Недавно с Вовой случилась беда. У него испортились несколько клавиш на клавиатуре, однако он все равно смог собрать все сокровища. Теперь Вову интересует вопрос, какое максимальное число клавиш он может испортить так, чтобы все равно быть способным собрать все сокровища.

Входные данные

В первой строке находится целое число n (1n1000) - количество ящиков с драгоценностями. Далее следуют n строк, по 2 целых числа в каждой - координаты очередного сундука. Эти числа не превышают по модулю 10^5.

Выходные данные

Выведите одно число - максимальное число клавиш, которое можно испортить.

Пример

Входные данные #1
4
0 0
2 0
0 2
2 2
Выходные данные #1
6
Входные данные #2
4
-1  0
2 0
2 2
0 2
Выходные данные #2
6
Источник 2008 Цикл интернет-олимпиад для школьников. Пятая индивидуальная олимпиада, 20 декабря, Задача A