Splitting the Field#10574
Farmer John's cows are all located at distinct positions in his two-dimensional field. FJ wants to enclose all of the cows with a rectangular enclosure whose sides are parallel to the - and -axes. He wants the enclosure to be as small as possible while still containing every cow; cows on the boundary are allowed.
Unfortunately, FJ is on a tight budget due to low milk production last quarter. He would therefore like to reduce the total area he needs to enclose, and the only way he can think of to do this is by building two enclosures instead of one.
Please help FJ determine how much area he can save, in total, by using two enclosures instead of one. As with the original enclosure, the two enclosures must collectively contain all the cows, with cows on their boundaries allowed, and their sides must be parallel to the - and -axes. The two enclosures must not overlap, even along their boundaries.
Note that enclosures with zero area are allowed. For example, an enclosure may have zero width and/or zero height.
The first line contains an integer n~(3 \le n \le 50000).
The next lines each contain two integers specifying the location of a cow. Cow locations are positive integers in the range from to 10^9.
Print one integer representing the total area FJ can save by using two enclosures instead of one.
Example 1