Setting the video P40128


Statement
 

pdf   zip

html

Professor Oak is a great fan of Takeshi’s castle. So much, that he has bought a satellite antenna to watch the show in several European channels. Professor Oak has a guide of all the channels of Europe, and wants to set his video to record as many episodes as possible. But it is not easy: The video only can record a channel at a time. Moreover, the episodes can have different lengths (depending on how they are edited, the advertiments, etc).

Can you help professor Oak? Write a program that, given the beginning time and end time of the broadcast of all the episodes of Takeshi’s castle in all the european channels during several days, computes the maximum number of episodes that can be recorded every day.

Input

Input consists of several cases. Each case has a natural number 1 ≤ n ≤ 105 followed by n pairs (i1, f1), …, (in, fn) of natural numbers that indicate the beginning time and the end time, both of them included, of each episode of a day. For any j between 1 and n, assume 0 ≤ ij ≤ fj ≤ 109.

Output

For each case of the input, print a line with the maximum number of complete episodes that professor Oak will be able to record that day.

Public test cases

  • Input

    3   100 200  500 780  1000 1040

7   400 1100  500 600  900 1400
200 300  1200 1300  100 700  800 1000

3   0 100  100 1439  0 1439

2   1234 1234  1234 1234

    Output

    3
4
1
1
    • Information
    Author
    Ricardo Martín
    Language
    English
    Translator
    Carlos Molina
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++ Python Python
    User solutions
    C++ Python