题目描述
埃及的尼罗河上有很多游轮,虽然可能分别属于不同的公司,但之间有个不成文的默契。当多艘游轮要靠岸时,一种可能是直接停靠在岸边的码头,另一种方式是靠在已经就位的船旁边。它们可以一艘接着一艘并排起来,离岸较远的船上的游客若要下船,则可以通过其它的船到达岸上。不过有个限制,就是离岸较近的船不可以比离岸较远的船先离开,不然就会被卡住出不去了。
给所有船只的到达和离开时间,问岸边最少需要几个码头,才能让所有的船有办法靠岸。
佔总分30%的测试数据中 n<=15
佔总分100%的测试数据中 n<=1000,并且所有数字皆不超过1000000000。
输入格式
输入的第一行有一个整数n,代表游轮的个数。
接下来有n行每一行分别有两个整数Ai,Bi(Ai<=Bi),代表第i艘游轮的到达和离开时间。
所有船只的到达和离开时间都不会相等。
输出格式
请输出能让所有船只靠岸的最少码头数。
样例输入
样例输出