SPOJ Brasil

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 C₀, C₁, . . . , C_N, onde C₀ é a mesma cidade que C_N, 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 L_i e G_i que representam respectivamente a latitude e longitude, em graus, de uma cidade servida pela companhia aérea (−89 ≤ L_i ≤ 89 e −180 ≤ G_i ≤ 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