Коровы Фермера Джона стоят в различных точках \((x_1, y_1) \ldots (x_n, y_n)\) его поля (\(1 \leq N \leq 1000\), все \(x_i\) и \(y_i\) - положительные нечётные целые числа, не превышающие \(1,000,000\). ФД хочет разделить своё поле изгородью бесконечной длины с севера на юг, описываемой уравнением \(x=a\) (\(a\) - чётное целое, так обеспечивается, что изгородь не пройдёт через позицию ни одной коровы). Также он хочет построить изгородь бесконечной длины с востока на запад, которая описывается уравнением \(y=b\), где \(b\) - чётное целое. Эти две изгороди пересекаются в точке \((a,b)\), и вместе делят поле на четыре региона.
ФД хочет выбрать \(a\) и \(b\) так, чтобы получить "сбалансированное" количество коров во всех регионах, т.е. чтобы не было региона, который содержит слишком много коров. Пусть \(M\) - максимальное количество коров в этих четырёх регионах, ФД хочет, чтобы \(M\) было как можно меньше. Помогите ФД определить это минимально возможное значение для \(M\).
ФОРМАТ ВВОДА (файл balancing.in):
Первая строка ввода содержит два целых числа, \(N\) и \(B\). Каждая из следующих \(n\) строк содержит местоположение одной коровы, указанное её координатами \(x\) и \(y\).
ФОРМАТ ВЫВОДА (файл balancing.out):
Выведите минимально возможное значение \(M\), которое может достичь ФД оптимальным расположением изгородей.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
7 3
5 5
7 13
3 1
11 7
5 3
9 1
|
2
|