Балансування навантаження (Платина)
Корови Фермера Джона розташовані в різних точках (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, яке фермер Джон може досягти, оптимально розташувавши огорожі.