Description

Farmer John is not good at multitasking. He often gets distracted and has trouble finishing long projects. Right now, he is trying to paint one side of his barn, but he keeps painting small rectangular regions and then gets sidetracked to take care of the cows, causing some parts of the barn to have more layers of paint than others.

We can describe one side of the barn as a 2D $x-y$ plane. Farmer John paints $n$ rectangles on this plane. The sides of each rectangle are parallel to the coordinate axes, and each rectangle is described by the coordinates of its bottom-left corner and top-right corner.

Farmer John wants to paint enough layers so that he will not need to repaint again in the near future. However, he does not want to waste time applying too much paint. It turns out that $K$ layers is the best amount. After he finishes painting all rectangles, help him determine how much area of the barn is covered by exactly $K$ layers of paint.

Input Format

The first line contains $n$ and $K$.

Each of the remaining $n$ lines contains four integers $x_1$, $y_1$, $x_2$, $y_2$, describing a painted rectangular region with bottom-left corner $(x_1,y_1)$ and top-right corner $(x_2,y_2)$. All $x$ and $y$ values are in the range from $0$ to $1000$, and all rectangles have positive area.

Output Format

Output the area of the barn that is covered by exactly $K$ layers of paint.

3 2
1 1 5 5
4 4 7 6
3 3 8 7

8

Hint

$1\le K\le n\le 10^5$.

The second problem of the USACO February 2019 contest, Silver division.

Translated by ChatGPT 5