Wild party P27158


Statement
 

pdf   zip

thehtml

Masao’s life is hard. He lives in New York, earns good money by working for one of the best companies in the world, and his flat is usually crowded by beautiful models with liberal behaviors. Now Masao wants to choose the best moment for a party, but with so many gorgeous girls in and out of his flat, he is a bit confused. Poor Masao, indeed… can you help him?

Given the arrival time and leaving time of every model, Masao would like to know the maximum number of models that will be at his flat at the same time. Additionally, he would like to know the length of that nice event. This way, Masao could plan the wildest possible party!

Input

Input consists of several cases. Every case begins with the number of models 1 ≤ n ≤ 105 (yes, 100000, Masao is like this). Follow n pairs of integer numbers a and ℓ, which state that a model arrives at time a and leaves at time ℓ, with 0 ≤ a < ℓ ≤ 109. A special case with n = 0 marks the end of input.

Output

For every case, print the number of models and the length of the wildest possible party.

Public test cases

  • Input

    2   0 1000   2000 3500
4   100 150  250 300  120 220  140 230
3   1000 3000   4500 6000   3500 4500
2   100 200   100 200
0

    Output

    1 1500
3 10
1 2500
2 100
    • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++