Балансировка нагрузки (Платина)
Коровы Фермера Джона стоят в различных точках (x[1], y[1]) ... (x[n], y[n]) его поля. ФД хочет разделить своё поле изгородью бесконечной длины с севера на юг, описываемой уравнением x = a (a - чётное целое, так обеспечивается, что изгородь не пройдёт через позицию ни одной коровы). Также он хочет построить изгородь бесконечной длины с востока на запад, которая описывается уравнением y = b, где b - чётное целое. Эти две изгороди пересекаются в точке (a, b) и вместе делят поле на четыре региона.
ФД хочет выбрать a и b так, чтобы получить "сбалансированное" количество коров во всех регионах, т.е. чтобы не было региона, который содержит слишком много коров. Пусть m - максимальное количество коров в этих четырёх регионах, ФД хочет, чтобы m было как можно меньше. Помогите ФД определить это минимально возможное значение для m.
Входные данные
Первая строка содержит одно целое число n (1 ≤ n ≤ 10^5). Каждая из следующих n строк содержит местоположение одной коровы, указанное её координатами x и y (положительные нечётные целые числа, не превышающие 10^6).
Выходные данные
Выведите минимально возможное значение m, которое может достичь ФД оптимальным расположением изгородей.