炎热的夏天到了,Bob准备在小镇上开一家冷饮店,开店选址是一门大学问,为了让自己的店火爆起来,Bob要精心选择自己的开店地址。
小镇的道路规划是横平竖直的。如果将小镇想象成坐标轴,小镇中任意两个房子(x_1,y_1)和(x_2,y_2)之间的距离,可以直接用曼哈顿距离来计算,也就是 = |x_1-x_2| + |y_1-y_2| 。
现在已经统计到了小镇上所有住户房子的坐标值,请你帮Bob选一下冷饮店的地址,使得该点到所有住户房子的距离和最小。(请注意:允许选到的开冷饮店的位置,是某住户房子的位置,也允许选到开冷饮电的位置,不是某住户房子的位置)
第1行输入一个整数 n ,代表了小镇有n个住户。(1 ≤ n ≤ 10000)
接下来 n 行,每行有 2 个整数 x 和 y,表示小镇中某个住户的房子的坐标值。(-10000 ≤ x,y ≤ 10000)
请输出Bob的冷饮店,到所有住户的房子距离和的最小值。
5 1 2 2 2 1 3 3 -2 3 3
10
【说明】
|x| 表示求 x 的绝对值,如果 x 是非负整数,则 x 的绝对值是自己,如果 x 是否负整数,则 x 的绝对值为相反数。比如,|2|=2,|-2|=2 。
【样例解释】
将Bob的冷饮店建在坐标 2,2 处,可以使得该点到所有住户距离的和最小。