CUTOUT - Cutting out

no tags 

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 x1, x2,...,x4r from the interval [0,n] separated by single spaces. For each i = 1,...,r, integers x4i-3, x4i-2, x4i-1, x4i describe the i-th rectangle: x4i-3 is the distance of its left side from the left side of the square, x4i-2 is the distance of its right side from the left side of the square, x4i-1 is the distance of the bottom side of the rectangle from the bottom side of the square and x4i 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 

hide comments
Ashwini: 2014-04-24 14:21:06

Last edit: 2014-05-28 19:38:02

Added by:adrian
Date:2004-06-08
Time limit:5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:III Polish Collegiate Team Programming Contest (AMPPZ), 1998