Задача №112783. Грибы
Соревнование по собиранию грибов в этом году будет проходить в прямоугольном лесу. Прямоугольная карта леса состоит из клеток площадью 1 квадратный метр.
Был составлен список из G грибов, растущих в лесу. Каждый гриб представлен координатами клетки на карте. Для того чтобы сделать соревнование наиболее честным для каждого из D участников, лес был разделен на D полос таким образом, чтобы максимальное количество грибов в каждой из полос было минимальным. Лес может быть разделен, либо только горизонтальными полосами, либо только вертикальными. Все полосы должны иметь ненулевую площадь, причем каждая клетка должна принадлежать ровно одной полосе. Помогите организаторам соревнования разделить лес на полосы оптимальным способом.
Первая строка содержит 4 целых числа X, Y, D, G. Ширина и высота поля описывается числами X и Y, а числа D и G описывают количество участников и количество грибов, соответственно. Следующие G содержат два числа 1 ≤ xi ≤ X, 1 ≤ yi ≤ Y – координаты грибов. \(2 \le D \le \max(X, Y)\)
Выведите максимальное количество грибов в одной из полос при оптимальном разделении леса.
4 5 2 8
1 1
1 2
1 3
2 1
2 2
2 3
3 4
3 4
4
Подзадача 1.
2 ≤ X, Y ≤ 20, 1 ≤ G ≤ 400. Решение оценивается в 13 баллов.
Подзадача 2.
2 ≤ X, Y ≤ 200, 1 ≤ G ≤ 400. Решение оценивается в 24 баллов.
Подзадача 3.
2 ≤ X, Y ≤ 1000, 1 ≤ G ≤ 104. Решение оценивается в 26 баллов.
Подзадача 4.
2 ≤ X, Y ≤ 105, 1 ≤ G ≤ 105. Решение оценивается в 37 баллов.