Codah ClubTrain. Submit. Improve.
Sign in
English
#000040

z-policajac

Mr. Little Z has found a job as a security guard, and his first assignment is to preserve the peace at a big New Year's party in Belgrade Arena. Unfortunately, irresponsible Mr. Little Z fell asleep right after he arrived. Now he has to read a report to his boss about the maximum number of people that were at the party at one time. Mr. Little Z decided to phone everyone who was at the party and ask them their exact time of arrival and departure from the party. The duration of the party Mr. Little Z represented by 1000000 discrete time intervals (he wants to be accurate).


Help Mr. Little Z give an accurate report that tells the maximum number of people that were at the party at one time.


InputThe first line of the standard input contains the number 0<N<=10000, where N corresponds to the number of people that attended the party. In the next N lines there are two numbers Ai and Bi , where Ai represents the interval in range [1..1000000] when the i-th guest arrived at the party and Bi represents the interval in range [1..1000000] when the i-th guest left the party. That means the i-th person was at the party in the interval between Ai and Bi , including intervals Ai and Bi .

OutputTo the standard output write one number that is the maximum number of people that were at the party at the same discrete interval (moment).


Input:
4
1 3
2 3
3 4
5 7
Output:
3

Explanation: At interval 3, persons 1, 2 and 3 were at the party.

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.