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 |
