Problem J: 城市中心

Problem J: 城市中心

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MiB

Description

大城市的道路是相互平行或垂直的,如果在城市的道路上行走,不能用点与点之间的直线距离计算长度,而是应该定义两个点(设坐标分别为 lns="http://www.w3.org/1998/Math/MathML">(x,y) 与 lns="http://www.w3.org/1998/Math/MathML">(x,y))的城市距离为

lns="http://www.w3.org/1998/Math/MathML">xx+yy

给定 lns="http://www.w3.org/1998/Math/MathML">n 个点的坐标,请在二维平面中找到一个聚会中心点,使得给定点到这个中心的城市距离之和最小,输出这个最小值。

Input

  • 第一行:单个整数 lns="http://www.w3.org/1998/Math/MathML">n
  • 第二行到第 lns="http://www.w3.org/1998/Math/MathML">n+1 行:第 lns="http://www.w3.org/1998/Math/MathML">i+1 行有两个整数 lns="http://www.w3.org/1998/Math/MathML">xi 和 lns="http://www.w3.org/1998/Math/MathML">yi,表示一个点的坐标。

数据范围

  • lns="http://www.w3.org/1998/Math/MathML">5000xi,yi5000
  • 对于 lns="http://www.w3.org/1998/Math/MathML">30% 的数据,lns="http://www.w3.org/1998/Math/MathML">1n20
  • 对于 lns="http://www.w3.org/1998/Math/MathML">60% 的数据,lns="http://www.w3.org/1998/Math/MathML">1n2000
  • 对于 lns="http://www.w3.org/1998/Math/MathML">100% 的数据,lns="http://www.w3.org/1998/Math/MathML">1n100000

Output

单个整数:表示各点到中心的距离之和的最小值。

Sample Input Copy

4
1 0
0 1
-1 0
0 -1

Sample Output Copy

4

HINT

最优中心应该设置在(0,0)处