UPA

A Unicamp organiza anualmente, sempre em agosto, a UPA – Unicamp Portas Abertas –, um evento em que alunos de escolas da região podem visitar e conhecer as atividades da Universidade. O evento recebe em um dia dezenas de milhares alunos, que chegam em ônibus.

Um dos grandes problemas da organização da UPA é o estacionamento dos ônibus que trazem os alunos. A Unicamp reserva uma longa avenida para que os ônibus estacionem, um em seguida ao outro, todos paralelos à avenida; para cada ônibus são reservados $20$ metros de avenida, com os espaços marcados no chão.

Para organizar o estacionamento, cada escola que chega de ônibus deve informar o horário de chegada e o horário de partida de seu ônibus, e os horários devem ser obedecidos rigorosamente. Dessa forma, o espaço de um ônibus que já partiu pode ser reutilizado por um outro ônibus que chega.

Dados os horários em que cada ônibus chega e parte, escreva um programa para calcular o menor espaço possível, em metros, que deve ser reservado para que todos os ônibus estacionem.

Entrada

A primeira linha contém um inteiro $N$, o número de ônibus que chegarão para a UPA. Os horários de chegada e partida são dados como números inteiros. Cada uma das $N$ linhas seguintes descreve um ônibus e contém dois inteiros $C_i$ e $P_i$, respectivamente o instante de chegada e o instante de partida do ônibus $i$. Dois ônibus $A$ e $B$ tais que $C_B \geq P_A$ ou $C_A \geq P_B$ podem utilizar o mesmo espaço de estacionamento. Assim, por exemplo, se o horário de chegada do ônibus $B$ e a partida do ônibus $A$ forem iguais, então o ônibus $B$ pode ocupar o espaço que o ônibus $A$ ocupou.

Saída

Seu programa deve produzir uma única linha, contendo um único inteiro, o menor comprimento da avenida, em metros, que deve ser reservado para o estacionamento de ônibus.

Restrições

• $1 \leq N \leq 100\ 000$
• $0 \leq C_i \leq 100\ 000$ para $1\leq i\leq N$
• $0 \leq P_i \leq 100\ 000$ para $1\leq i\leq N$
• $C_i < P_i$ para $1\leq i\leq N$

Informações sobre a pontuação

A tarefa vale $100$ pontos. Estes pontos estão distribuídos em subtarefas, cada uma com suas restrições adicionais às definidas acima:

• Subtarefa 1 (12 pontos): $P_i = 1 + C_i$ para $1\leq i\leq N$
• Subtarefa 2 (29 pontos): $N \leq 1\ 000, C_i\leq 1\ 000$ e $P_i\leq 1\ 000$
• Subtarefa 3 (27 pontos): É garantido que a resposta é menor do que $1\ 000$ metros.
• Subtarefa 4 (32 pontos): Nenhuma restrição adicional.

Seu programa pode resolver corretamente todas ou algumas das subtarefas (elas não precisam ser resolvidas em ordem). Sua pontuação final na tarefa é a soma dos pontos de todas as subtarefas resolvidas corretamente por alguma das suas submissões.

Exemplos

Exemplo de entrada 1

3
100 360
300 500
200 400

Exemplo de saída 1

60

Explicação do exemplo 1: Explicação do exemplo 1: há três ônibus. O primeiro chega no instante $100$ e parte no instante $360$, o segundo chega no instante $300$ e parte no instante $500$, e o terceiro chega no instante $200$ e parte no instante $400$. A figura abaixo ilustra o tempo em que cada ônibus utiliza o estacionamento. A resposta é $60$ metros (espaço para $3$ ônibus).

Exemplo de entrada 2

4
500 560
200 340
80 200
400 540

Exemplo de saída 2

40

Explicação do exemplo 2: há quatro ônibus. O primeiro chega no instante $500$ e parte no instante $560$, o segundo chega no instante $200$ e parte no instante $340$, o terceiro chega no instante $80$ e parte no instante $200$, e o quarto chega no instante $400$ e parte no instante $540$. A figura abaixo ilustra o tempo em que cada ônibus utiliza o estacionamento. A resposta é $40$ metros (espaço para $2$ ônibus) – por exemplo, os ônibus $1$ e $2$ podem usar um dos espaços e os ônibus $3$ e $4$ podem usar o outro.