[AMPPZ2014]The Captain

时间限制:20s      空间限制:256MB

题目描述

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


输入格式

第一行包含一个正整数n(2<=n<=200000),表示点数。
接下来n行,每行包含两个整数x[i],y[i](0<=x[i],y[i]<=10^9),依次表示每个点的坐标。


输出格式

一个整数,即最小费用。


样例输入

5
2 2
1 1
4 5
7 1
6 7

样例输出

2

提示

没有写明提示


题目来源

鸣谢Claris上传