该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题面描述

学校里有 $n$ 个教室，第 $i$ 个教室的坐标为 $(x_i,y_i)$。

食堂管理员想把送餐车放在其中一个教室里。
如果把送餐车放在坐标 $(x,y)$ 的教室，那么教室 $(x_i,y_i)$ 到送餐车的距离定义为：

也就是曼哈顿距离。

请你求出：把送餐车放在哪个教室时，所有教室到送餐车的距离和最小，并输出这个最小值。

输入

第一行输入一个整数 $n$。 $(1\leq n \leq 10^3)$ 接下来 $n$ 行，每行输入两个整数 $x_i,y_i$。 $(1 \leq x, y \leq 10^9)$

输出

输出一个整数，表示最小距离和。

输入输出样例 #1

输入

3
0 0
1 0
0 1

输出

2