Fence Optimization

Farmer John's \(N\) cows (where \(5 \leq N \leq 50,000\)) are located at distinct positions in a 2D field. He wants to enclose all of his cows with a rectangular fence whose sides are parallel to the x and y axes. The fence should be as small as possible while still containing every cow (cows on the boundary are allowed).

Unfortunately, Farmer John's budget is tight. He is willing to sell up to three cows from his herd in order to greatly reduce the area enclosed by the fence.

Your task is to compute the smallest possible area of the fence after removing no more than three cows. Note that cows are to be treated as points and the fence as four line segments. In particular, the answer can be zero if, after removing cows, all the remaining ones lie on a common vertical or horizontal line.

Formally, if you have a set \(S\) of cow points \((x_i,y_i)\) after removal, you must choose boundaries \(x_{min}, x_{max}, y_{min}, y_{max}\) satisfying
\(x_{min} \le x_i \le x_{max}\) and \(y_{min} \le y_i \le y_{max}\) for all \( (x_i,y_i)\) in \(S\). The area of the fence is given by \[ \text{area} = (x_{max} - x_{min}) \times (y_{max} - y_{min}). \] Your goal is to minimize this area.

inputFormat

The first line contains the integer \(N\). Each of the next \(N\) lines contains two space-separated integers \(x_i\) and \(y_i\) representing the position of a cow.

outputFormat

Output a single integer, which is the minimum possible area of the fence after removing up to three cows.

sample

5
1 1
2 3
4 2
10 10
9 6

3