Rock Festival

Time limit1sMemory limit256 MB

Summary

Add up the areas of rectangles that touch by edge or corner and print the largest connected patch.

Level: Medium7 of 10
Topics: Union-find, Geometry, Sorting
Solved: No attempts yet

Problem

A rock festival came to Deokhwi's town and the band he likes played there. The townspeople like quiet, so they drove the band out. Deokhwi got angry and decided to invite the band to the backyard of his own mansion and ask for a show.

The backyard has not been used for a long time, so weeds grew here and there. Deokhwi does not want to mow them, so he will use the largest patch of bare ground as the stage. The bare ground consists of several rectangles, and rectangles that touch each other count as one patch. Two rectangles that meet at a single corner point also count as touching.

Find the area of the largest patch of bare ground in the backyard.

Input

The first line contains the number of weed free plots $N$ . ( $0 < N \le 50000$ )

Each of the next $N$ lines describes one plot as $X$ , $Y$ , $W$ , $H$ in that order. It is the rectangle whose lower left corner is $(X, Y)$ , whose width is $W$ , and whose height is $H$ . ( $0 < W, H \le 500$ )

Every side of every plot is parallel to the $x$ axis or the $y$ axis. $X$ , $Y$ , $X+W$ , and $Y+H$ all fit in a signed 32 bit integer. The interiors of two different plots never overlap.

Output

Print the area of the largest patch of bare ground on the first line.

Hint

In the first example the 8 plots split into four patches. The fourth and fifth plots form a patch of area 16, the second and eighth form a patch of area 20, the first, third, and seventh form a patch of area 15, and the sixth alone forms a patch of area 16. So the answer is 20.

Examples3

Example 1

Input

Expected output

Example 2
Input
```
1
0 0 500 500
```
Expected output
```
250000
```
Example 3
Input
```
2
0 0 2 2
2 2 3 3
```
Expected output
```
13
```