Minimal Rectangle Covering

You are given N points in the coordinate system. Your task is to cover all these points with one or more rectangles such that the following conditions are met:

• Each rectangle has its sides parallel to the coordinate axes.
• The center of each rectangle is at the origin, i.e. the point \((0,0)\).
• Every given point is located either inside or on the boundaries of at least one rectangle.

Although it is always possible to cover all points with a single rectangle, that rectangle might have a very large surface area. Instead, you must choose one or more rectangles so that the sum of their surface areas is minimized.

A rectangle covering a set of points (S) (with each point ((x,y))) must have half-width at least (\max_{(x,y)\in S} |x|) and half-height at least (\max_{(x,y)\in S} |y|). Thus, the area of such a rectangle is [ A(S) = 4 \times \Bigl(\max_{(x,y)\in S} |x|\Bigr) \times \Bigl(\max_{(x,y)\in S} |y|\Bigr). ]

Output the minimal total area required to cover all points. You may assume that (N) is small enough (e.g. (N \le 16)) to allow an exponential time solution using bitmask dynamic programming.

inputFormat

The input consists of the following:

The first line contains a single integer \(N\), the number of points.
Each of the following \(N\) lines contains two integers, representing the coordinates \(x\) and \(y\) of a point.

outputFormat

Output a single integer: the minimal sum of the surface areas of the rectangles covering all points, according to the criteria above.

sample

1
1 1

4