Given the locations and dimensions of stones in the park, compute the area of the stoned surface with the largest area.
The input file contains several test cases, each of them as described below.
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.
Constraints:
| 0 < N ≤ 50 000 | Number of stones. |
| 0 < W ≤ 500, 0 < H ≤ 500 | Dimensions of stones. |
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).
For each test case, write to the output a single line with an integer: the area of the stoned surface with largest area.
The following figure represents the configuration of stones described in the sample input.
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.