5998 - 专用牛棚

约翰的N头奶牛实在是太难伺候了,她们甚至有自己独特的产奶时段.当 然对于某一头奶牛,她每天的产奶时段是固定的,为时间段AB包括时间段A和时间段B.

显然,约翰必须开发一个调控系统来决定每头奶牛应该被安排到哪个牛棚去挤 奶,因为奶牛们显然不希望在挤奶时被其它奶牛看见.

约翰希望你帮他计算一下:如果要满足奶牛们的要求,并且每天每头奶牛都要被挤过奶,至少需要多少牛棚。

输入

第一行输入一个正整数N.

接下来N行每行输入两个整数A,B,如题目描述

输出

输出最少需要多少个牛棚

样例

输入

5
1 10
2 4
3 6
5 8
4 7

输出

4

提示

数据规模

对于100\%的数据,1 < N < 50000,  1 \le A \le B \le 10^6

来源

USACO
时间限制 1 秒
内存限制 256 MB
讨论 统计
上一题 下一题