eolymp
bolt
Try our new interface for solving problems
Problems

City Park

City Park

Time limit 1 second
Memory limit 128 MiB

Porto is blessed with a beautiful city park. The park, in the western section of the city, borders the Atlantic Ocean. It has great lawns, small forests, plenty of flowerbeds, a variety of ponds, and, in all, lots of points of interest. Porto families love the park and flock to in on weekends and holidays.

With such multitudes, it is hard work to keep the lawns in good shape. In order to control the movements of the crowd, the engineers of the municipality designed a system of paths connecting points of interest. These paths are built with large rectangular shale stones from the nearby Milhária quarry. Using sophisticated location systems, the engineers were able to lay the stones perfectly aligned with the north-south direction (and hence also with the east-west direction). Stones linking one from one point of interest to another touch each other, forming a contiguous stoned surface, and do not touch any stones belonging to any other stoned surface.

The “defend our park” movement wants to stage a demonstration in the park to publicise their cause. Since they do not want to harm the lawns, they must stage the demonstration in one of those stoned surfaces. In order to summon as many supporters as possible, but not too many, they need to find out the area of the stoned surface with largest area.

Given the locations and dimensions of stones in the park, compute the area of the stoned surface with the largest area.

Input data

The first line contains one positive integer n, representing the number of rectangular stones. n lines follow, each one describing the location and dimensions of a stone, by four integers x, y, w, h, where (x, y) are the coordinates of the location of the lower left corner the stone, w is its length along the x-axis, and h is its length along the y-axis.

It is guaranteed that, for the given inputs, the coordinates of the stone corners can be handled using normal 32-bit signed integers, as well as the total area of any stoned surface. For every pair of distinct stones, the area of the intersection of the two rectangles that represent them in the park is zero (i.e., there are no overlaps).

Output data

Print a single integer: the area of the stoned surface with largest area.

Example

The following figure represents the configuration of stones described in the sample input.

prb7917.gif

There are 4 stoned surfaces: one made up by stones 3 and 4, on the left, with area 16; another, made up by stones 7 and 1, with area 20; a third one, below the previous, made up by stones 0, 2 and 6, with area 15; and the one on the right, made up by stone 5 only, with area 16. The largest area is 20.

Examples

Input example #1
8
14 1 2 2
16 9 1 5
11 3 5 2
3 4 2 5
5 9 3 2
21 3 2 8
13 2 1 1
13 8 3 5
Output example #1
20
Source 2014 ACM Southwestern Europe Regional Contest (SWERC), Problem F