Новорічний снігопад#1433
Король маленької, але гордої африканської держави вирішив, що на Новий Рік у його країні обов'язково має випасти сніг. Для цього він наказав придбати спеціальних пристроїв для керування погодою. Ці пристрої були куплені, встановлені й активовані — і дійсно, пішов сніг.
Король був задоволений успіхом свого плану. Проте виявилося, що інтенсивність снігу в різних частинах країни відрізняється. Звісно ж, король хоче святкувати Новий Рік у місці з найбільшою інтенсивністю снігу. Ваше завдання — допомогти йому знайти таке місце.
Карта країни змодельована у вигляді площини з декартовою системою координат. Кожен пристрій встановлено у точці з цілими координатами й підвищує інтенсивність снігу рівно на у всіх точках з цілими координатами, які лежать на межах квадратів з такими властивостями:
Довжини сторін квадратів мають вигляд 4k+2, де — невід'ємне ціле число.
Сторони квадратів паралельні осям координат.
Центр кожного квадрата збігається з точкою, у якій встановлено пристрій.
Пристрій не впливає на інтенсивність снігу в інших точках площини.
На наступній ілюстрації показано, як працює пристрій:
На ілюстрації жовта точка в центрі означає пристрій. Точки, у яких пристрій підвищує інтенсивність снігу на , виділені червоним.
Перший рядок містить ціле число (1 \leq N \leq 1000).
Далі в наступних рядках записано координати пристроїв керування погодою. Кожен рядок містить координати одного пристрою у форматі "", де — -координата, а — -координата (-1000000 \leq x, y \leq 1000000). Жодні два пристрої не встановлені в одній точці.
Виведіть єдине ціле число — максимальну інтенсивність снігу у будь-якій точці площини.
Приклад 1