Intermediário Informática - Semana 24

A Pedra Filosofal

A Universidade Federal da Fronteira Sul (UFFS) foi criada no dia 15 de setembro de 2009, tendo suas atividades de ensino, pesquisa e extensão começado em 29 de março de 2010 em prédios provisórios alugados. Atualmente, a UFFS possui 6 campi, nas cidades de: Chapecó, Laranjeiras do Sul, Realeza, Cerro Largo, Erechim e Passo Fundo. Em Chapecó, a mudança dos prédios provisórios para o campus ocorreu no 2º semestre de 2013.

No prédio provisório em que funcionava o curso de Ciência da Computação funcionavam também vários outros cursos, como o curso de Defesa contra as Artes das Trevas, mas havia somente 3 laboratórios, 2 auditórios e 1 pedra filosofal. Todos os pesquisadores interessados em usar a pedra filosofal precisavam fazer suas requisições com no mínimo uma semana de antecedência. Com base na lista de requisições feitas para a semana, o secretário decidia quais requisições atender visando minimizar o tempo em que a pedra filosofal ficaria ociosa. A pedra filosofal ficava disponível para uso 12 horas por dia, o que corresponde a 3.600 minutos por semana. Numerando-se, então, esses 3.600 minutos de 1 a 3.600, cada pesquisador, ao fazer sua requisição, deveria informar o minuto a partir do qual gostaria de começar a usar a pedra filosofal e o minuto a partir do qual a pedra filosofal estaria livre para ser usada por outro pesquisador.

Escreva um programa capaz de gerenciar as requisições conforme descrito. Nós nos encarregaremos de voltar no tempo para entregar seu programa ao secretário.

Entrada

A primeira linha da entrada é constituída por um único inteiro N (1 ≤ N ≤ 1000), o qual representa o número de requisições que foram feitas para a semana. Cada uma das N linhas seguintes, por sua vez, descreve uma requisição através de dois inteiros i e j (1 ≤ i < j ≤ 3.600), os quais representam respectivamente o minuto a partir do qual o pesquisador gostaria de começar a usar a pedra filosofal e o minuto a partir do qual a pedra filosofal estaria livre para ser usada por outro pesquisador.

Saída

Imprima uma única linha contendo o número máximo de minutos da semana em que é possível não deixar a pedra filosofal ociosa.

Exemplo de Entrada Exemplo de Saída
5
1 1200
960 2880
3360 3600
1680 2160
2640 3600
2639