The Siruseri Welfare Association has organized a Cultural Programme for families in the
area, to build up community spirit. The Cultural Programme is being held at the Siruseri
Community Hall. Inside the hall, children perform songs and dances. Outside, local restau-
rants have set up stalls selling snacks.
As is typical on such an occasion, members of the audience drift in and out of the hall
during the programme. An observant office bearer of the Siruseri Welfare Association notes
down the times at which people enter and leave the hall. At the end of the day, he wonders
what the maximum size of the audience was during the course of the programme.
For convenience, he writes down each time as a single integer, the number of minutes
from the start of the programme. Also, the door of the hall is narrow, so at any time, either
one person can enter or one person can leave the hall, but not both. Thus, each entry and
exit time that is noted down is distinct.
For example, suppose the observations noted down are the following. Each line denotes
the entry time and exit time of one person. (The identity of the person is not important�the
same person may enter and leave the hall many times. For instance, in the example below,
it might well be that the entries and exits recorded at Serial Nos 2 and 5 refer to the same
person.)
Serial No Enters at Leaves at
1 1 7
2 2 4
3 6 9
4 3 8
5 5 10
In this example, the maximum size of the audience during the programme was 4. This
was achieved between time 6 and 7.
Your task is to read the list of entry and exit times and compute the maximum size of
the audience during the programme.
Input format
The first line of input is a single integer, N, the number of entries and exits recorded. This
is followed by N lines of input. Each of these lines consists of two integers, separated by
a space, describing one entry and exit. The first integer is the entry time and the second
integer is the exit time.
Output format
A single integer, denoting the maximum size of the audience during the performance.
1
Test data
For all inputs, 1  N  105. In 70% of the cases, N  5000. The entry and exit times for
each person are in the range {0, 1, . . . , 107}. All entry and exit times are guaranteed to be
distinct. For each person, the entry time is guaranteed to be strictly before the exit time.
Example
Sample input
5
1 7
2 4
6 9
3 8
5 10