XXVI Olimpíada Brasileira de Informática
Submeta sua solução

Nome do arquivo: carrinho.x, onde x deve ser c, cpp, java, js ou py

Carrinho

Um carrinho elétrico, que usa apenas uma bateria com carga inicial de C coulombs, tem uma característica incrível: ele só pode ir à velocidade constante mas pode escolher qualquer velocidade constante, maior do que zero, de V metros por segundo. Só que quanto maior a velocidade, menor a autonomia. Quer dizer, de maneira mais rigorosa, a distância máxima dmax metros que ele pode percorrer é diretamente proporcional à carga inicial da bateria e inversamente proporcional à velocidade: dmax = C/V. É incrível mas veja que, mesmo que a carga seja muito pequena, o carrinho sempre pode percorrer qualquer distância, desde que vá a uma velocidade suficientemente pequena!

O carrinho está na posição zero de uma pista reta com comprimento D metros. Há N baterias, com diferentes cargas, colocadas em posições distintas ao longo da pista, uma delas na posição zero. Considere que nosso carrinho ideal consegue fazer um pit-stop instantâneo, trocando de bateria sem perder tempo algum. Ao passar por uma nova bateria ele pode decidir ou não fazer a troca; e ele pode alterar sua velocidade apenas num instante em que troca de bateria. Qual é o tempo mínimo possível para o carrinho chegar ao final da pista?

Entrada

A primeira linha da entrada contém um inteiro N e um real D, respectivamente, o número de baterias e o comprimento da pista. As N linhas seguintes contêm, cada uma, dois reais P e C definindo, respectivamente, a posição e a carga das baterias. Sempre existe uma bateria na posição 0.0 e as baterias são dadas em ordem estritamente crescente de posição.

Saída

Imprima uma linha contendo um real, com exatamente três casas decimais, o tempo mínimo possível em segundos para o carrinho chegar ao final da pista.

Restrições

  • 1 ≤ N ≤ 1000 e 1.0 ≤ D ≤ 10000.0
  • 0.0 ≤ P < D e 0.0 < C < 100.0

Exemplos

Entrada
4 10.000
0.000 1.000
1.200 0.100
3.000 10.000
7.700 1.000
Saída
13.900
	

 

Promoção
logo sbc
Patrocínio
Apoio
Coordenação