Фермер Джон красит одну сторону своего амбара маленькими прямоугольными
областями, однако его отвлекают коровы, и в результате некоторые участки
содержат больше слоёв краски, чем другие.
Мы можем описать эту сторону амбара как двумерную плоскость, на которой
ФД красит \(N\) прямоугольников, стороны каждого из которых параллельны осям
координат, и каждый из которых описывается своим левым нижним и правым верхним
углами.
ФД хочет применить несколько слоёв краски к амбару, чтобы не пришлось
перекрашивать в ближайшем будущем. Однако он не хочет тратить время
делая лишние слои краски. Он считает \(K\) оптимальным числом слоёв краски.
Помогите ФД определить, какая площадь будет покрыта ровно \(K\) слоями краски
после того, как он закрасит все свои прямоугольники.
ФОРМАТ ВВОДА (файл paintbarn.in):
Первая строка ввода содержит \(N\) и \(K\) (\(1 \leq K \leq 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 1000\), все прямоугольники имеют положительную
площадь.
ФОРМАТ ВЫВОДА (файл paintbarn.out):
Выведите площадь амбара, которая покрыта ровно \(K\) слоями краски.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2
1 1 5 5
4 4 7 6
3 3 8 7
|
8
|