City Park#7917

City Park

1 secondo

128 megabyte

Difficile

Porto is famous for its beautiful city park. In the western part of the city, the park borders the Atlantic Ocean. It features well-kept lawns, small forests, numerous flower beds and ponds, as well as various attractions. The residents of Porto love this park and often visit it on weekends and public holidays.

However, with such a large flow of visitors, maintaining the lawns in good condition is not easy. To manage the movement of people, the municipal engineers designed a system of paths connecting points of interest. These paths are paved with large rectangular slate slabs quarried from the nearby Milharia quarry. Using precise location methods, the engineers laid the stones perfectly aligned along the north–south and east–west directions. Stones forming a single path from one point of interest to another fit tightly together, creating a continuous stone surface, and they do not touch stones belonging to any other surface.

The movement "Protect Our Park" decided to hold a demonstration in the park to draw attention to their demands. Since the activists do not want to damage the lawns, they must gather on one of these stone surfaces. To attract as many supporters as possible, but not too many, they need to choose the stone surface with the largest area.

Given the positions and dimensions of the stones in the park, calculate the area of the largest stone surface.

Input

The first line contains one positive integer $n (0 < n \leq 50000)$ n~(0 < n \le 50000) — the number of rectangular stones.

The following $n$ lines describe the stones. Each stone is given by four integers $x, y, w, h (0 < w \leq 500, 0 < h \leq 500)$ x, y, w, h~(0 < w \le 500, 0 < h \le 500), where:

$x, y$ — the coordinates of the bottom-left corner of the stone,
$w$ — the stone's length along the $x$ -axis,
$h$ — the stone's length along the $y$ -axis.

It is guaranteed that 32-bit signed integers are sufficient to solve the problem. For each pair of distinct stones, their intersection area is zero (that is, there are no overlaps).

Output

Print one integer — the area of the largest stone surface.

Esempi

The following figure shows the configuration of stones given in the input:

There are $4$ stone surfaces:

the surface consisting of stones $3$ and $4$ on the left — area $16$ ;
the surface consisting of stones $7$ and $1$ — area $20$ ;
the surface below the previous one, consisting of stones $0$ , $2$ , and $6$ — area $15$ ;
the surface on the right, consisting only of stone $5$ — area $16$ .

The largest area is $20$ .

Esempio 1