附加文件

问题描述

在一个操场的一侧直线跑道上摆放着 N 个石子，每个石子有一种颜色。

第 i 个石子距离跑道最左侧的距离为 Xi，颜色为 Ci。任意两个石子的位置都不相同。

现在要选择一段区间，使得该区间包含所有颜色的石子，且该区间的长度最短。

输出这个最短区间的长度。

输入

第一行：一个整数 N

接下来 N 行：每行两个整数 Xi, Ci

输出

一个整数，表示满足题意的最短区间的长度

样例输入

6 
25 5 
26 1 
15 1 
22 2 
20 1 
30 2

样例输出

4

样例解释

数据规模

对于 50%的数据： 1≤N≤300；

对于 100%的数据：1≤N≤50,000；0≤Xi≤1,000,000,000；1≤Ci≤1,000,000,000；