Problema dos fazendeiros trabalhadores (USACO)

Tradução do problema Milking Cows da USACO (http://ace.delos.com/usacoprob2?a=rRnbNp27COM&S=milk2)

Dificuldade Única

Três fazendeiros acordam à 5 toda manhã e se dirigem ao curral para ordenhar três vacas. O primeiro fazendeiro começa a ordenhar sua vaca no tempo 300 (mensurado em segundos corridos após às 5) e termina no tempo 1000. O segundo fazendeiro começa no tempo 700 e termina no tempo 1200. O terceiro fazendeiro começa no tempo 1500 e termina no tempo 2100. O maior tempo contínuo durante o qual no mínimo um fazendeiro ordenhava uma vaca foi de 900 segundos (do tempo 300 ao tempo 1200). O maior tempo onde nenhuma ordenha foi feita durante a primeira e a última ordenha foi de 300 segundos (1500 menos 1200).

Seu trabalho é escrever um programa que examine uma lista de tempos iniciais e finais para N (1<=N<=5000) fazendeiros e compute (em segundos):

• O intervalo de tempo mais longo onde pelo menos uma vaca era ordenhada.
• O intervalo de tempo mais longo (depois do início da primeira ordenha) durante o qual nenhuma vaca foi ordenhada.

Formato da entrada

• Linha 1: Um único inteiro.
• Linha 2..(N+1): Com dois inteiros não negativos menores que 1000000, representado o tempo em segundos de início e de fim da ordenha de cada fazendeiro.

Nome do arquivo de entrada: milk2.in.

Exemplo de entrada

3
300 1000
700 1200
1500 2100

Formato de saída

Uma única linha com dois inteiros que representam [respectivamente] o maior tempo contínuo de ordenha e ocioso.

 Nome do arquivo de saída: milk2.out.

Exemplo de saída

900 300