Фермер Джон красит одну сторону амбара маленькими прямоугольниками.
Но его отвлекают коровы, и некоторые части амбара красятся чаще,
чем другие.
Мы можем описать эту сторону амбара как двумерную плоскость, на которой
ФД рисует \(N\) прямоугольников, стороны которых параллельны осям координат,
Прямоугольники описываются координатами левого нижнего и правого верхнего углов.
ФД хочет покрасить амбар в несколько слоёв, так чтобы не пришлось
вскорости снова красить. Однако, он не хочет тратить время на лишнюю покраску.
Сначала он решил, что оптимально покрасить \(K\) раз. Однако оглядев область
Амбара, покрашенную ровно \(K\) раз, он решил добавить два прямоугольника,
Так, чтобы максимально увеличить площадь, покрашенную ровно \(K\) раз, так
чтобы эти прямоугольники не имели общей ненулевой площади пересечения.
Заметим, что он может рисовать ноль новых прямоугольников или только
один прямоугольник, если это может улучшить результат.
ФОРМАТ ВВОДА (файл paintbarn.in):
Первая строка ввода содержит \(N\) и \(K\) (\(1 \leq K, N \leq 10^5\)).
Каждая из оставшихся \(N\) строк содержит четыре целых числа \(x_1, y_1, x_2, y_2\)
описывающих прямоугольный регион левым нижним углом \((x_1, y_1)\) и
правым верхним углом \((x_2, y_2)\). Все величины \(x\) и \(y\) в интервале
\(0 \ldots 200\), и все прямоугольники имеют положительную площадь.
Как и уже нарисованные прямоугольники, новые должны иметь положительную
площадь, а координаты их углов \(x\) и \(y\) должны быть в интервале \(0 \ldots 200\).
ФОРМАТ ВЫВОДА (файл paintbarn.out):
Выведите максимальную площадь амбара, которая может быть покрыта ровно \(K\)
слоями краски, если ФД закрасит ещё до двух дополнительных непересекающихся
(по площади) прямоугольника.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2
1 1 4 4
3 3 7 6
2 2 8 7
|
26
|