Балансировка нагрузки (Бронза)
Балансировка нагрузки (Бронза)
Коровы Фермера Джона стоят в различных точках (x1
, y1
) ... (xn
, yn
) его поля (все xi
и yi
- положительные нечётные целые числа, не превышающие b. ФД хочет разделить своё поле изгородью бесконечной длины с севера на юг, описываемой уравнением x = a (a - чётное целое, так обеспечивается, что изгородь не пройдёт через позицию ни одной коровы). Также он хочет построить изгородь бесконечной длины с востока на запад, которая описывается уравнением y = b, где b - чётное целое. Эти две изгороди пересекаются в точке (a, b), и вместе делят поле на четыре региона.
ФД хочет выбрать a и b так, чтобы получить "сбалансированное" количество коров во всех регионах, т.е. чтобы не было региона, который содержит слишком много коров. Пусть m - максимальное количество коров в этих четырёх регионах, ФД хочет, чтобы m было как можно меньше. Помогите ФД определить это минимально возможное значение для m.
Входные данные
Первая строка содержит два целых числа n (1 ≤ n ≤ 100) и b (b ≤ 106
). Каждая из следующих n строк содержит местоположение одной коровы, указанное её координатами x и y.
Выходные данные
Выведите минимально возможное значение m, которое может достичь ФД оптимальным расположением изгородей.
7 10 7 3 5 5 9 7 3 1 7 7 5 3 9 1
2