Programming is an art!
When asked about his salary by attendees at the Winter School 2011, Petr Mitrichev gave a tactful response:
– Compared to L – a lot, but compared to R – a little.
As for the identities of these mysterious L and R, Petr chose to remain discreet…
While contemplating an engaging topic for his presentation at the Winter School 2011 in Kharkiv, Petr was brainstorming various thematic options. However, he quickly dismissed them, as they were already familiar and had been covered by others. Yet, as a true artist-programmer adept in advanced techniques, he couldn't settle for an ordinary topic.
I'll talk about L and R – especially since it seems no one has covered this yet, – Petr decided, and he began drafting a lecture plan and sketching problem diagrams. Luckily, his workplace had an ample supply of markers in various colors, which he used to draw the diagrams. If a part of the diagram didn't satisfy him, Petr simply took a marker of a different color and painted over the unsatisfactory section with a new color that matched the revised point in the plan.
Through this process of redrawing, he realized that it could be turned into an interesting problem.
A programmer uses N markers of different colors to draw N segments on a coordinate line. Given the left (L) and right (R) endpoints of each segment, determine the maximum number of different colors that can be visible in the final drawing. This number will be referred to as the level of this artist-programmer.
Input
The first line of the input contains a natural number N (1 ≤ N ≤ 300). The following N lines each contain a pair of numbers L and R separated by a space (-10^9 ≤ L_i < R_i ≤ 10^9).
Output
Output a single number: the desired maximum level of the artist-programmer.