题目描述

给定平面上的 $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

数据规模与约定

对于 $100\%$ 的数据，$2\leq n\leq 2\times 10^5$，$0\leq x_i,y_i\leq 10^9$。