J13 例题-6 平面上的点

题目描述

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

输入格式

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

输出格式

一个整数，即最小费用。

样例输入

5
2 2
1 1
4 5
7 1
6 7

样例输出

2

样例分析

如上所述。

数据范围

对于 $30\%$ 的数据：$n \leq 1000$； 对于 $100\%$ 的数据：$n \leq 200000$。