A museum runs n scheduled tours during the day. Tour i occupies the half-open time range [start_i, end_i): a guide leading it is busy from start_i up to, but not including, end_i. A single guide can lead any number of tours back-to-back as long as they never overlap in time (a guide freed at time t can immediately start a tour that begins at t).
Every tour must be staffed by exactly one guide, and a guide cannot lead two overlapping tours simultaneously. Print the minimum number of guides needed to staff all tours.
Input format
Line 1: an integer n.
Next n lines: two integers start_i end_i describing tour i.
Output format
A single integer: the minimum number of guides required.
Constraints
- 1 <= n <= 40
- 0 <= start_i < end_i <= 1000