该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

A. 大合照（photo）

题目描述

宇宙联合国正在召开第十届联盟会议，会议期间来自不同行星的诸位代表、领袖邀请知名摄影师小A帮他们拍一张集体照，因为人数众多，但是为了体现行星种族的多样性，至少要保证集体照中每个行星的代表至少出现一位。

此时，共有 $n$ 位代表出现在宴会厅内，恰好在一条直线的不同坐标上，为了保证照片的清晰度，同时满足领袖们的需求的前提下，小A希望照片的宽度越小越好（照片的宽度=照片的终点坐标−照片的起点坐标）。

请你帮小A算算，这张照片宽度的最小值是多少？

输入

第一行是一个正整数 $n$，表示代表的总数量。 接下来 $n$ 行，每行包含两个正整数，分别表示该代表的坐标 $x$ 和 所属行星的编号 $id$。

输出

输出一个整数，代表照片的最小宽度。

样例

输入

5
4 4
5 4
7 5
8 7
9 9

输出

4

输入

10
1 3
10 3
9 2
6 3
8 3
5 3
2 2
7 2
3 3
4 1

输出

2

输入

6
25 7
26 1
15 1
22 3
20 1
30 1

输出

4

说明

【样例1解释】 直线上共有5名代表。 在坐标4的位置有 $id=4$ 的代表。 在坐标5的位置有 $id=4$ 的代表。 在坐标7的位置有 $id=5$ 的代表。 在坐标8的位置有 $id=7$ 的代表。 在坐标9的位置有 $id=9$ 的代表。 从坐标5开始到坐标9结束拍照，可以确保行星编号为4 5 7 9的代表，都能出现在合照上，因此照片的最小宽度 $9-5=4$。

【数据范围】

• 对于10% 的数据，满足 $1 \le N \le 30,\ 1 \le x \le 1000,\ 1 \le id \le 5$。
• 对于50% 的数据，满足 $1 \le N \le 1000$，满足 $1 \le x \le 1000,\ 1 \le id \le 1000$。
• 对于100% 的数据，满足 $1 \le N \le 5\times 10^4,\ 1 \le x \le 10^9,\ 1 \le id \le 10^9$。