Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

VIAGEM08 - Viagem de volta ao mundo

Grandes companhias aéreas como Air France, Lufthansa e American Airlines oferecem bilhetes de “volta ao mundo”, que permitem uma certa flexibilidade na escolha das cidades a serem visitadas durante a viagem. Neste tipo de bilhete, com preço fixo, os clientes podem escolher os trechos a serem voados para completar viagem de volta ao mundo. No entanto, as companhias colocam algumas restrições sobre como as viagens podem ser montadas. As restrições diferem dependendo da companhia, mas tipicamente referem-se ao número de trechos voados, ao número de cidades em um mesmo país que podem ser visitadas, ou à milhagem total da viagem. Muitas companhias colocam ainda a restrição de que a viagem só pode ser feita em uma direção (continuamente para o leste ou continuamente para o oeste).

Rosaura pretende comprar um bilhete de volta ao mundo de uma companhia que tem restrições um pouco diferentes. A principal diferença é que a companhia definiu que a tarifa de um trecho voado com o bilhete de volta ao mundo entre duas cidades é simplesmente a diferença de latitude entre essas cidades, e a companhia coloca um limite na soma das tarifas dos trechos escolhidos. Mais especificamente, as restrições do bilhete de volta ao mundo que Rosaura pretende adquirir são as seguintes:

  • a viagem deve iniciar e terminar na mesma cidade; 
  • nenhum trecho da viagem pode ir para o oeste (pode ir para o leste, para o norte ou para o sul); 
  • a viagem deve dar exatamente uma volta ao mundo (ou seja, a viagem não pode cortar o meridiano da cidade de partida);
  • para uma viagem de volta ao mundo que visite sequencialmente as cidades C0, C1, . . . , CN, onde C0 é a mesma cidade que CN, a soma 

deve ser menor ou igual a um valor máximo estipulado pela companhia. Essa soma é denominada pela companhia como a tarifa total da viagem de volta ao mundo;

  • a viagem não pode cruzar os pólos (as regiões de latitude maiores que 89 ou menores que −89 são muito perigosas para as aeronaves da companhia e não podem ser sobrevoadas).

Rosaura quer visitar o maior número possível de cidades durante a sua viagem de volta ao mundo, e pediu que você escreva um programa que, dados o mapa com as cidades com vôos da companhia aérea e o valor da tarifa total máxima de um bilhete, determine qual o número máximo de cidades que Rosaura pode visitar.

Entrada

A entrada contém um único conjunto de testes, que deve ser lido do dispositivo de entrada padrão (normalmente o teclado). A primeira linha do conjunto de testes contém dois números inteiros N e T que indicam respectivamente o número de cidades servidas pela companhia aérea (2 ≤ N ≤ 500) e a tarifa total máxima permitida (0 ≤ T ≤ 500).

Cada uma das N linhas seguintes contém um par de inteiros Li e Gi que representam respectivamente a latitude e longitude, em graus, de uma cidade servida pela companhia aérea (−89 ≤ Li ≤ 89 e −180 ≤ Gi ≤ 179 para 1 ≤ i ≤ N). A primeira cidade (ou seja, a cidade cujas coordenadas aparecem na primeira das N linhas) é a cidade onde a viagem será iniciada e terminada.

 

Saída

Seu programa deve imprimir, na saída padrão, uma linha contendo um inteiro, o número máximo de cidades que Rosaura pode visitar com seu bilhete de volta ao mundo, partido e chegando na cidade indicada na entrada.

Exemplo

Entrada:
3 177
0 -50
89 100
-89 180

Saída:
0

Entrada:
5 0
30 0
30 10
30 11
30 100
30 179

Saída:
4

Entrada:
14 40
3 5
10 10
20 20
20 -40
20 -30
20 -20
10 -41
10 -31
10 -19
-40 22
-40 -42
-40 -32
-40 -22
-40 -10

Saída:
6


Adicionado por:Wanderley Guimarăes
Data:2012-07-17
Tempo limite:1s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP PERL6 PY_NBC SCALA TCL
Origem:Seletiva IOI 2008

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.