На плоскости есть \(n\) отрядов, пронумерованных от \(1\) до \(n\), \(i\)-й отряд находится в точке с целочисленными координатами \((x_i, y_i)\). Все отряды находятся в различных точках.
Бримстоун должен посетить каждый отряд как минимум один раз. Вы можете выбрать, с каким отрядом в одной точке изначально находится Бримстоун.
Чтобы перейти от одного отряда к другому, Бримстоун выбирает одно из четырех направлений движения (вверх, вниз, вправо или влево) и двигается в этом направлении с постоянной скоростью — один единичный отрезок в секунду — до тех пор, пока не придёт к какому-либо отряду. Как только он приходит к какому-либо отряду, он может повторить этот процесс.
Каждые \(t\) секунд происходит огненный ливень, и в эти моменты Бримстоун должен находиться в одной точке с любым своим отрядом. Он может сколько угодно времени стоять на месте в одной точке с любым отрядом.
Бримстоун хороший командир, поэтому до начала обхода он может собрать не более одного нового отряда и поставить его в любую точку плоскости с целочисленными координатами, в которой не стоит ни один отряд. Обратите внимание, что он также должен будет посетить новый отряд хотя бы один раз.
Помогите Бримстоуну, найдите минимальное целое положительное \(t\) такое, что обход можно произвести, добавив не более одного отряда. Если такого \(t\) не существует, вы должны сообщить об этом.
Выходные данные
Выведите единственное целое число — минимальное время \(t\), такое что обход всех отрядов можно произвести, добавив не более одного нового отряда.
Если ни одного такого \(t\) не существует, выведите \(-1\).
Примечание
В первом примере из условия можно добавить отряд в точку \((0, 0)\), после чего все отряды можно будет обойти при \(t = 100\). Можно доказать, что при \(t < 100\), даже добавив не более одного нового отряда, не получится сделать обход, поэтому ответ \(100\).
Во втором тесте из условия нельзя посетить все отряды ни при каком \(t\), даже при добавлении не более одного нового отряда, поэтому ответ \(-1\).
В третьем тесте можно добавить отряд в точку \((1, 0)\), и тогда все отряды можно будет обойти при \(t = 2\). Можно доказать, что это минимальное такое \(t\).
В четвертом тесте не нужно добавлять новый отряд и можно обойти все отряды при \(t = 2\). Можно доказать, что это минимальное такое \(t\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
100 0
0 100
-100 0
0 -100
|
100
|
|
2
|
7
0 2
1 0
-3 0
0 -2
-1 -1
-1 -3
-2 -3
|
-1
|
|
3
|
5
0 0
0 -1
3 0
-2 0
-2 1
|
2
|
|
4
|
5
0 0
2 0
0 -1
-2 0
-2 1
|
2
|