Farmer John's Optimal Repainting

Farmer John has painted N axis‐aligned rectangles on the barn wall, each described by the coordinates of its bottom‐left and top‐right corners. As a result, some parts of the barn have been painted with different numbers of coats. The barn wall is modeled as the X–Y plane, and each rectangle adds one coat of paint to the area it covers.

Farmer John believes that K coats is optimal – not too little and not too much. Unfortunately, due to his distracted painting style, only a small area of the barn currently has exactly K coats. To improve this without wasting paint, he is allowed to add at most two extra new rectangles. Each new rectangle also adds one coat of paint to its area. However, these extra rectangles must be non‐intersecting (two rectangles that share only a boundary or corner are allowed, but if their overlapping area is greater than 0, they are considered intersecting). He may choose to add zero, one, or two extra rectangles.

A point’s final number of coats is its original number plus one if it lies in one of the extra rectangles that cover it. Note that if a point initially had exactly K coats, painting over it will change it to K+1 coats, which is undesirable. Conversely, if a point initially had K-1 coats and we paint over it, it becomes exactly K coats – a benefit.

Your task is to help Farmer John choose up to two extra non‐intersecting rectangles (or choose not to add any) so that the total area that ends up with exactly K coats of paint is maximized. The input consists of N rectangles and the desired number of coats K. Each rectangle is given by its bottom‐left and top‐right coordinates. The output is the maximum possible area that can have exactly K coats after adding the extra rectangle(s).

Note on the effect of an extra rectangle:

• If a point has K-1 coats, adding paint will make it exactly K (beneficial).
• If a point already has K coats, adding an extra coat will ruin it (detrimental).
• Points with any other number of coats are unaffected (treated as 0 benefit).

Hint: After processing the original N rectangles, you may use a grid (via coordinate compression) to determine for each cell its current coat count and area. Then, define a weight for each cell: if its coat count is K-1, the cell has a benefit equal to its area; if its coat count is exactly K, painting over it subtracts its area (since it would then become K+1); otherwise the cell’s weight is 0. The problem then reduces to finding up to two non‐overlapping subrectangles (in this weighted grid) with maximum total sum.

inputFormat

The first line contains two integers N and K (1 ≤ N ≤ 100, 1 ≤ K ≤ 10⁹). Each of the next N lines contains four integers: x₁ y₁ x₂ y₂ (with x₁ < x₂ and y₁ < y₂), describing a painted rectangle. All coordinates are integers.

Note: The rectangles may overlap.

outputFormat

Output a single integer — the maximum total area that can have exactly K coats of paint after adding at most two extra non‐intersecting rectangles.

sample

1 1
1 1 3 3

4