#1359. [Baltic2009]Candy

内存限制:64 MiB 时间限制:10 Sec

题目描述

给定N个数对(S_i,T_i),表示时刻S_i时在位置T_i处出现一粒糖果。有一些机器人可供使用,每个机器人可花费一
单位时间向相邻位置移动。要求用最少的机器人接到全部糖果。时刻0时机器人位置可自行安排。
1≤N≤100000, 
0≤S_i,T_i≤10^9。

输入格式

 第一行包含一个整数 n,表示该轮生产所产生的糖果数量。
接下来的 n 行中,第 i 行包含两个整数 s_i 和 t_i,表示第 i 个糖果的产生位置和时间。

输出格式

样例

样例输入


			
5
1 1
2 3
1 5
3 4
2 6

样例输出


			
2
样例解释:
在时刻1的时候,有两个糖果在不同的位置掉下,因此需要两个机器人分别赶到位置1和位置5
在时刻2的时候,也有两个糖果在不同的位置掉下,因此需要两个机器人分别赶到位置3和位置6
在时刻3的时候,只有一个糖果掉下,因此需要一个机器人赶到位置4
所以对于5颗糖果需要的机器人编号分别为1 1 2 1 2

数据范围与提示