题目描述

给定平面上的$n$个点的坐标，规定$(x_1,y_1)$到$(x_2,y_2)$的费用为$min(|x_1-x_2|,|y_1-y_2|)$，求从$1$号点走到$n$号点的最小费用。

输入格式

第一行有一个正整数$n$，表示点的个数；

接下来$n$行，每行包含两个整数$x[i]$,$y[i]$，依次表示每个点的坐标。

输出格式

一个整数，即最小费用。

样例

5
2 2
1 1
4 5
7 1
6 7

2

提示

样例1解释

$(2,2)$ -> $(1,1)$ -> $(7,1)$ -> $(6,7)$

数据范围

$2\le n \le 2*10^5$，$0\le x[i],y[i] \le 10^9$