F. Огненный ливень
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На плоскости есть $$$n$$$ отрядов, пронумерованных от $$$1$$$ до $$$n$$$, $$$i$$$-й отряд находится в точке с целочисленными координатами $$$(x_i, y_i)$$$. Все отряды находятся в различных точках.

Бримстоун должен посетить каждый отряд как минимум один раз. Вы можете выбрать, с каким отрядом в одной точке изначально находится Бримстоун.

Чтобы перейти от одного отряда к другому, Бримстоун выбирает одно из четырех направлений движения (вверх, вниз, вправо или влево) и двигается в этом направлении с постоянной скоростью — один единичный отрезок в секунду — до тех пор, пока не придёт к какому-либо отряду. Как только он приходит к какому-либо отряду, он может повторить этот процесс.

Каждые $$$t$$$ секунд происходит огненный ливень, и в эти моменты Бримстоун должен находиться в одной точке с любым своим отрядом. Он может сколько угодно времени стоять на месте в одной точке с любым отрядом.

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

Помогите Бримстоуну, найдите минимальное целое положительное $$$t$$$ такое, что обход можно произвести, добавив не более одного отряда. Если такого $$$t$$$ не существует, вы должны сообщить об этом.

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

В первой строке находится единственное целое число $$$n$$$ $$$(2 \le n \le 1000)$$$ — изначальное количество отрядов.

В каждой из следующих $$$n$$$ строк содержатся два целых числа $$$x_i$$$, $$$y_i$$$ $$$(|x_i|, |y_i| \le 10^9)$$$ — координаты $$$i$$$-го отряда.

Гарантируется, что все точки различны.

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

Выведите единственное целое число — минимальное время $$$t$$$, такое что обход всех отрядов можно произвести, добавив не более одного нового отряда.

Если ни одного такого $$$t$$$ не существует, выведите $$$-1$$$.

Примеры
Входные данные
4
100 0
0 100
-100 0
0 -100
Выходные данные
100
Входные данные
7
0 2
1 0
-3 0
0 -2
-1 -1
-1 -3
-2 -3
Выходные данные
-1
Входные данные
5
0 0
0 -1
3 0
-2 0
-2 1
Выходные данные
2
Входные данные
5
0 0
2 0
0 -1
-2 0
-2 1
Выходные данные
2
Примечание

В первом примере из условия можно добавить отряд в точку $$$(0, 0)$$$, после чего все отряды можно будет обойти при $$$t = 100$$$. Можно доказать, что при $$$t < 100$$$, даже добавив не более одного нового отряда, не получится сделать обход, поэтому ответ $$$100$$$.

Во втором тесте из условия нельзя посетить все отряды ни при каком $$$t$$$, даже при добавлении не более одного нового отряда, поэтому ответ $$$-1$$$.

В третьем тесте можно добавить отряд в точку $$$(1, 0)$$$, и тогда все отряды можно будет обойти при $$$t = 2$$$. Можно доказать, что это минимальное такое $$$t$$$.

В четвертом тесте не нужно добавлять новый отряд и можно обойти все отряды при $$$t = 2$$$. Можно доказать, что это минимальное такое $$$t$$$.