Submit | All submissions | Best solutions | Back to list |

## CUTOUT - Cutting out |

One has to cut out a number of rectangles from a paper square. The sides of each rectangle are to be parallel to the sides of the square. Some rectangles can be already cut out. What is the largest area of a rectangle which can be cut out from the remaining paper?

### Illustration

Three rectangles have been cut out from the square 10x10 in the figure shown below. The area of the largest rectangle that can be cut out from the remaining paper is 16. One of such rectangles is shown with a dashed line.

### Task

Write a program that for each data set from a sequence of several data sets:

- reads descriptions of a square and rectangles from the input,
- computes the area of the largest rectangle which can be cut out from the remaining paper,
- writes the result to output.

### Input

The first line of the input file contains one positive
integer d not larger than 10. This is the number of data sets. The data sets
follow. Each set of data occupies two consecutive lines of the input file. The
first line of each data set contains two integers n and r, 1 <=
n <= 40000, 0 <= r <= 100. The integer n is the length
of the sides of an input square. The integer r is the number of rectangles which have been cut out from the
square. The second line of the data set contains a sequence of 4r integers x_{1}, x_{2},...,x_{4r} from the interval
[0,n] separated by single spaces. For each i = 1,...,r, integers x_{4i-3}, x_{4i-2}, x_{4i-1}, x_{4i}
describe the i-th rectangle: x_{4i-3} is the distance of its left side from the left side of the square, x_{4i-2}
is the distance of its right side from the left side of the square, x_{4i-1} is the distance of the bottom side of the rectangle from the
bottom side of the square and x_{4i} is the distance of its top side from the bottom side of the square.

### Output

For each i = 1,...,d, your program should write only one integer to the i-th line of the output file -- the largest area of a rectangle which can be cut out from the rest of the i-th square.

### Example

Sample input: 2 6 2 0 3 0 3 3 6 3 6 10 3 0 5 0 5 0 10 5 10 9 10 0 5 Sample output: 9 20

Added by: | adrian |

Date: | 2004-06-08 |

Time limit: | 5s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | C CPP C++ 4.3.2 CPP14-CLANG CPP14 JAVA NODEJS PYTHON PYTHON3 |

Resource: | III Polish Collegiate Team Programming Contest (AMPPZ), 1998 |