Description

在二维平面上定义(x1,y1)(x2,y2)两点间的距离为:|x2-x1|+|y2-y1| 给 n 个点,求 n 个点的某点,使得该点到其他点的距离总和最小

Input

输入包含多组数据 每组数据第1行:n 表示有 n 个点 ( 1 <= n <= 100000 ) 第 2 到 n+1 行每行一个坐标(x,y)

Output

每组数据输出一行,为距离总和的最小值

Sample Input

4 2 3 1 1 3 2 4 4

Sample Output

8

Source

经典问题