Problem Description

You are given N points in the coordinate system. They need to be covered with one or more rectangles, such that the following conditions are met:

• The sides of each rectangle are parallel with the coordinate axes,
• The center of each rectangle is at the origin, i.e., point (0, 0),
• Each given point is located either inside the rectangle or on its boundaries.

It is possible to cover all the points using only one rectangle, but this rectangle could have a very large surface area. Our goal is to find a selection of required rectangles such that the sum of their surface areas is minimal.

Input Format

The first line of input contains the integer N (1 ≤ N ≤ 5000), the number of points.

Each of the following N lines contains two integers X and Y (-50,000,000 ≤ X, Y ≤ 50,000,000, XY ≠ 0), the coordinates of each point.

Output Format

You must output the required minimal sum of surface areas of the rectangles.

Sample Input and Output

Sample Input #1

2
1 1
-1 -1

Sample Output #1

4

Sample Input #2

3
-7 19
9 -30
25 10

Sample Output #2

2080

Sample Input #3

6
1 20
3 17
5 15
8 12
9 11
10 10

Sample Output #3

760

Notes

In test cases worth 40% of total points, it will hold N ≤ 20.

Clarification of the first test case: We choose the rectangle whose opposite angles are the given points, since it meets the conditions from the task.

Clarification of the second test case: We choose two rectangles with their centers at the origin. The first is of dimensions 50 x 20 and covers point (25, 10). The second is of dimensions 18 x 60 and covers the first two points. If we wanted to cover all the points using one rectangle, it would be of dimensions 50 x 60.

见题面 Input 部分

见题面 Output 部分