10461 - 产品加工

明明的工厂需要生产 n 个产品,每个产品会在记录本上记录开始生产的时间 x 以及完成生产的时间 y。(即相应产品在这些时间点 x,x+1,\dots,y 上都在生产线上)

现在明明拿到这本记录本以后想知道最多有多少件产品同时在生产线上生产。

输入

第一行只有一个整数 n,表示记录本上共记录了 n 件产品的信息。

接下来 n 行,每行两个整数 xy,表示一件产品开始生产的时间和完成生产的时间。

输出

一个整数,表示最多有多少件产品同时在生产线上生产。

样例

输入

4
2 6
8 9
1 5
1 2

输出

3

提示

数据范围

对于40\%的数据中,1 \leq n \leq 1000, 1 \leq x \leq y \leq 1000

对于80\%的数据中,1 \leq n \leq10^5, 1 \leq x \leq y \leq 10^5

对于100\%的数据中,1 \leq n \leq10^5, 1 \leq x \leq y \leq 10^8

时间限制 1000 毫秒
内存限制 1024 MB
统计
上一题 下一题