Minimum Runways Required

You are given a list of flights, each represented by its starting and ending times. The task is to compute the minimum number of runways required so that no two flights are using the same runway simultaneously.

In formal terms, given a set of intervals ( [s_i, e_i) ) for ( i = 1, 2, \ldots, n ), determine the smallest integer ( R ) such that all intervals can be assigned to one of ( R ) runways without overlapping intervals on the same runway. Use an efficient sweep line algorithm to solve this problem.

inputFormat

The input consists of several lines. Each line contains two integers representing the start and end time of a flight. The input is terminated by a line containing two -1 values (i.e. -1 -1), which should not be processed.

outputFormat

Output a single integer which is the minimum number of runways required so that no two flights overlap.## sample

1 5
2 6
8 12
5 9
-1 -1

2