## BPC 1 S6 - Painters

View as PDF

Points: 30 (partial)
Time limit: 3.0s
Memory limit: 256M

Authors:
Problem type

Rich with loot from the temple, you purchased a house and hired a team of workers to renovate it. This team has a strange way of painting. Instead of fully covering a wall with paint, like a normal crew, the worker paints a rectangle whose lower-left corner is and whose upper-right corner is . Rectangles can overlap, and the crew won't necessarily cover the entire wall. You just arrived home and saw the workers painting a wall the wrong colour. You still have time to tell workers to stop and prevent them from painting their rectangle. Find the minimum possible area that will be covered when everyone is done painting.

#### Constraints

##### Subtask 3 [65%]

No additional constraints.

#### Input Specification

The first line contains two integers, and .

The following lines each contain four integers, , , , .

#### Output Specification

Output one line containing a single integer, the minimum area covered by paint.

#### Sample Input 1

3 0
1 1 3 3
2 2 4 4
5 1 7 7

#### Sample Output 1

19

#### Explanation for Sample 1

A total of units will be covered by paint.

#### Sample Input 2

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

#### Sample Output 2

22

#### Explanation for Sample 2

It is optimal to tell the first or fourth painter not to paint their rectangle.

## Comments

There are no comments at the moment.