Problem D
Page Layout

Image from Curly Turkey

When you are designing a complicated document, page layout is important. Newspapers and magazines don’t just put a whole bunch of text that covers the page left-to-right, listing one article after another. They put multiple articles on a page, at different positions designed to maximize visual impact. The problem is that each story has a certain size and preferred (fixed) location, and you can’t fit all the stories on a single page (and stories can’t overlap). What you would like to do is maximize the amount of space you can fill with the stories you have on a single page. Then later, you’ll fill in the remaining space with pictures or advertising.

Input

Input consists of up to $500$ test cases. Each test case begins with an integer $1 \leq n \leq 20$, followed by $n$ story descriptions. Each story description consists of four integers: $w$, $h$, $x$, $y$. These represent the width, height, x-position, and y-position of the story. Each story has the shape of a rectangle, and $(x,y)$ is the location of the top-left corner. Every story will fit within the bounds of the rectangle defined by the corners $[0,0]$ and $[1000,1000]$. The last test case is followed by a single zero.

Output

For each test case, output the maximum area of the page that can be covered by the given stories. Two stories are considered overlapping if the area of their intersection is non-zero. In other words, stories may just touch each other by sharing an edge or a corner.

3
10 10 0 0
10 10 10 10
10 10 0 10
3
10 10 1 0
10 10 10 10
10 10 0 10
3
10 10 0 1
10 10 10 10
10 10 0 10
4
100 100 100 100
100 100 150 100
100 100 100 150
100 100 150 150
0

300
300
200
10000