题目翻译

在坐标系中给你 N 个点。 它们需要被一个或多个矩形覆盖，从而满足以下条件：

每个矩形的边与坐标轴平行，

每个矩形的中心都在原点，即点 (0, 0)，

每个给定点要么位于矩形内部，要么位于其边界上。

当然，可以只使用一个矩形来覆盖所有点，但是这个矩形可能具有非常大的表面积。 我们的目标是找到所需的矩形，使其表面积之和最小。

题目描述

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 in the origin, i.e. point (0, 0),
• Each given point is located either inside of the rectangle or on its boundaries.

Of course, 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.

输入格式

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.

输出格式

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

样例 #1

样例输入 #1

2
1 1
-1 -1

样例输出 #1

4

样例 #2

样例输入 #2

3
-7 19
9 -30
25 10

样例输出 #2

2080

样例 #3

样例输入 #3

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

样例输出 #3

760

提示

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

Clarification of the first test case: ​我们选择对角为给定的矩形 分，因为它符合任务的条件。

Clarification of the second test case: ​我们选择两个中心在原点的矩形。 这 第一个尺寸为 50 x 20 并覆盖点 (25, 10)。 第二个尺寸为 18 x 60，覆盖前两个点。 如果我们想用一个矩形覆盖所有点，它将是 尺寸 50 x 60。