#4152. [AMPPZ2014]The Captain

题目描述

给定平面上的n个点，定义(x1,y1)到(x2,y2)的费用为min(|x1-x2|,|y1-y2|)，求从1号点走到n号点的最小费用。

输入格式

第一行包含一个正整数n(2<=n<=200000)，表示点数。

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

输出格式

一个整数，即最小费用。

样例

样例输入

5  

2 2  

1 1  

4 5  

7 1  

6 7

样例输出

2  

数据范围与提示