1239 - 植树节(planting)

通过次数

9

提交次数

40

时间限制 : 1 秒
内存限制 : 128 MB

植树节快要到了,学校要组织志愿者去给树苗浇水。 有一排树苗,编号依次是 0,1,2, . . . 。 现有 n 个志愿者去给树苗浇水,第 i 个志愿者选定了一个区间 [a_i,b_i] ,表示第 i 个志愿者 将 [a_i,b_i] 这一区间内的每一棵树都浇一次水。 如某个志愿者选择的浇水区间为 [4,9] ,表示他将给编号为 4,5,6,7,8,9 的树各浇水一次。 当所有的志愿者完成各自所选区间的浇水后,可能有些树苗被不同的志愿者浇水多次,也 可能有的树苗一次也没被浇过水。 请你求出浇水最多的树苗被浇了多少次。

输入

第 1 行,一个整数 n ,表示志愿者的人数。

第 2 行到第 n + 1 行,每行两个整数 a_i,b_i( i= 0,1,2, . . . n − 1) ,表示志愿者 i 选择的浇水区间。

输出

输出 1 行, 1 个整数,表示浇水最多的树苗被浇水的次数。

样例

输入

4
0 2 
2 4 
1 4 
6 7

输出

3

输入

4
1000000 1000000 
1000000 1000000 
0 1000000 
1 1000000

输出

4

提示

对于所有的数据:n \leq 10^50 \leq a_i \leq b_i \leq 10^6

测试点编号a_i \leqb_i \leqn \leq特殊性质
1,2,310^310^310^3
4,5,6,710^610^610^5
810^610^610^5a_i=b_i
910^610^610^5a_i=1,b_i=10^3
1010^610^610^5

来源

CSP-J2022