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