Two Enclosures Problem

Farmer John has N cows (3 \leq N \leq 50{,}000) in his two-dimensional field, each at a distinct position. He wants to enclose all cows with a rectangular fence whose sides are parallel to the x and y axes, and the rectangle is as small as possible so that it contains every cow (cows on the boundary are allowed).

Due to budget constraints, Farmer John is considering building two enclosures instead of one, so that the total enclosed area is minimized. The two enclosures must collectively contain all the cows (with cows on the boundaries allowed) and must have sides parallel to the axes. However, the two enclosures are not allowed to overlap -- not even on their boundaries. Note that enclosures of zero area are legal (for example, an enclosure with zero width and/or zero height).

Your task is to compute how much less area Farmer John needs to enclose by using two enclosures instead of one. Formally, if the area of the minimum bounding rectangle that encloses all cows is \(A_{total}\) and the minimum total area using two non-overlapping rectangles is \(A_{two}\), then you should output \(A_{total} - A_{two}\). The formulas for the areas are given by:

Overall enclosure area: \(A_{total} = (x_{max}-x_{min}) \times (y_{max}-y_{min})\).

Each enclosure's area is calculated similarly. The solution involves trying all valid ways to split the cows into two groups (either with a vertical line or a horizontal line that leaves a gap between enclosures) and computing the difference in area. All formulas should be interpreted in \(\LaTeX\) format.

inputFormat

The first line contains a single integer \(N\) (\(3 \leq N \leq 50{,}000\)). Each of the next \(N\) lines contains two space-separated integers representing the \(x\) and \(y\) coordinates of a cow. All cow positions are distinct.

outputFormat

Output a single integer representing the amount of area saved by using two non-overlapping enclosures instead of one, i.e., \(A_{total} - A_{two}\).

sample

6
4 2
8 10
1 1
9 12
14 7
2 3

107