1022: 奶牛排队

内存限制:128 MB 时间限制:1.000 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:92 通过:33

题目描述

农夫约翰雇佣了一个专业的摄影师来给他的奶牛拍照。由于约翰的奶牛有很多的种类,他要求摄影师至少给他的每个种类的奶牛拍一张照片。

农夫约翰命令他的N只奶牛都排好队站在一条直线上,每只奶牛有一个位置的坐标和种类的序号。约翰要求摄影师沿着从某只奶牛开始沿着坐标的递增顺序给奶牛拍照,直到每种奶牛都至少有一张照片。这里,我们定义摄影师的工作量是在完成任务的前提下,坐标最大的奶牛的坐标值和坐标最小的奶牛的坐标值差距值。

约翰请你帮忙算出摄影师完成这个任务的最小工作量。

输入格式

第一行一个N,表示奶牛的数量。

接下来第2行到第N+1行,每行两个整数,第一个表示奶牛的坐标,第二个整数表示奶牛的种类。

输出格式

有且只有一行一个整数,表示最小的工作量。

输入样例 复制

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

输出样例 复制

4

数据范围与提示

数据范围:1<=N<=50000,坐标和种类的序号是不大于10亿的正整数。
说明:样例中,我们取坐标为22到26之间的奶牛拍照,所有的种类1,3,7都在了,所以答案是26-22=4。